2019ICPC上海网络赛部分题解

终于又打进去了一个名额。

A.Lighting Rounting I

B.Light blubs

题目大意为:给你$n$个$0$到$n-1$编号的灯初始全部是灭的。给你$m$次操作,每次操作将$[l,r]$区间内的灯转置,问在$m$次操作后还有几盏灯是亮的。

由于数据范围的问题,我刚开始还直接按照差分前缀和去做,然后TLE了。
这个题如果我们观察的话,对于一个区间$[l,r]$,可以将$[0,n-1]$分成三个区间:$[0,l-1]$,$[l,r]$,$[r+1,n-1]$,能够看出每个区间的开头元素为$[0,l,r+1]$,$0$不用管,因此灯泡反转的位置即为$l,r+1$,总共有$m$次操作,因此灯泡一共反转$2*m$次,所以我们将这$2*m$个数保存起来然后从小到大排序统计每个区间有几个灯泡是亮的即可。复杂度为O(T*m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
// bitset<maxn>bits;
struct node{
int x,tag;
}a[maxn];
bool cmp(node i,node j){
return i.x<j.x;
}
int main()
{
int T,n,m,l,r;
scanf("%d",&T);
for(int t=1;t<=T;t++){
int cnt=1;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d",&a[cnt].x,&a[cnt+1].x);
a[cnt++].tag=0;
a[cnt].x++;
a[cnt++].tag=1;
}
sort(a+1,a+cnt,cmp);
int res=0,cur=0;
for(int i=1;i<cnt;i++){
res+=cur*(a[i].x-a[i-1].x);
cur^=1;
}
printf("Case #%d: %d\n",t,res);
}
return 0;
}

C.Tirple

题目大意为:给你三个大小为$n$的集合,每个集合中的数字表示长度为$a_i$的木棍,问从这三个集合中各任意挑出一根木棍,这三根木棍恰好拼成一个三角形的方案数有多少。

FFT入门题目,题目类似于HDU4609
分两种情况讨论:当$n$小于等于1000时,我们可以直接$n^2$暴力求解;当$n$大于1000时,我们使用FFT 去求解:
首先我们找出三个集合每个的FFT ,然后对这三个数组两两求IFFT,这样我们就能求出两个集合的组合情况。我们假设从第三个集合的取出的为最长的一条边,那么我们就可以删掉不符合条件的方案,即$\sum c[i]*sum[i]$ ,其中$c[i]$为枚举的第三条边,$sum[i]$为小于$c[i]$的方案数。因为总的方案数为$n^3$,因此总方案数减去不符合的方案数即为最终的方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double pi=acos(-1);
const int maxn=400000+10;
struct cpx{
double x,y;
cpx friend operator*(cpx i,cpx j){return {i.x*j.x-i.y*j.y,i.x*j.y+i.y*j.x};}
cpx friend operator+(cpx i,cpx j){return {i.x+j.x,i.y+j.y};}
cpx friend operator-(cpx i,cpx j){return {i.x-j.x,i.y-j.y};}
};
ll r[maxn];
ll a[maxn],b[maxn],c[maxn];
ll sa[maxn],sb[maxn],sc[maxn];
cpx la[maxn],lb[maxn],lc[maxn],q[maxn];
ll n,ans,limit=1<<18;
void init(int limit,int bit_len){
for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(bit_len-1));
}
void fft(cpx* a,int limit,int flag){
for(int i=0;i<limit;i++){
if(i<r[i]){
swap(a[i],a[r[i]]);
}
}
for(int i=1;i<limit;i<<=1){
cpx part{cos(pi/i),flag*sin(pi/i)};
int R=i<<1;
for(int j=0;j<limit;j+=R){
cpx w{1,0};
for(int k=0;k<i;k++,w=w*part){
cpx x=a[j+k];
cpx y=w*a[j+i+k];
a[j+k]=x+y;
a[j+i+k]=x-y;
}
}
}
if(flag==-1){
for(int i=0;i<limit;i++){
a[i].x/=limit;
}
}
}
void solve1(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sa[b[i]+c[j]]++;
sb[a[i]+c[j]]++;
sc[a[i]+b[j]]++;
}
}
for(int i=1;i<=100000;i++){
sa[i]+=sa[i-1];
sb[i]+=sb[i-1];
sc[i]+=sc[i-1];
}
for(int i=0;i<n;i++){
ans-=sa[a[i]-1]+sb[b[i]-1]+sc[c[i]-1];
}
printf("%lld\n",ans);
}
void count(cpx *a,cpx *b,ll *c){
for(int i=0;i<limit;i++) q[i]=a[i]*b[i];
fft(q,limit,-1);
ll sum=0;
for(int i=0;i<=100000;i++){
ans-=sum*c[i];
sum+=(ll)(q[i].x+0.5);
}
}
void solve2(){
for(int i=0;i<n;i++){
sa[a[i]]++;
sb[b[i]]++;
sc[c[i]]++;
}
for(int i=0;i<limit;i++){
la[i]=cpx{sa[i],0};
lb[i]=cpx{sb[i],0};
lc[i]=cpx{sc[i],0};
}
fft(la,limit,1);
fft(lb,limit,1);
fft(lc,limit,1);
count(la,lb,sc);
count(lb,lc,sa);
count(la,lc,sb);
printf("%lld\n",ans);
}
int main()
{
init(limit,18);
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++){
ll x;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(sa,0,sizeof(sa));
memset(sb,0,sizeof(sb));
memset(sc,0,sizeof(sc));
scanf("%lld",&n);
ans=n*n*n;
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
for(int i=0;i<n;i++) scanf("%lld",&b[i]);
for(int i=0;i<n;i++) scanf("%lld",&c[i]);
printf("Case #%d: ",t);
if(n<=1000) solve1();
else solve2();
}
return 0;
}

D.Counting Sequences I

题目大意为:让你找一个长度为$n(n\geq 2)$的数组,使得$a_1+a_2+…+a_n=a_1*a_2*…*a_n$,问总共有多少种这样的数组。

这个题没什么算法可言,就直接$dfs$暴力求解即可,当然不能太暴力,需要尽可能的优化,我在最后大概对于$n=3000$的数据,4秒左右能跑出来,因此直接本地打表就过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//这段代码可修改为本地打表,3000个数字大约为20~30分钟之间
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=3000+10;
const ll mod=1e9+7;
ll res=0;
ll fac[maxn];
ll inv[maxn];
int m[maxn][maxn],n,limit;
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void init(){
fac[0]=1; for(int i=1;i<=3000;i++) fac[i]=fac[i-1]*i%mod;
inv[0]=1; for(int i=1;i<=3000;i++) inv[i]=qp(fac[i],mod-2);
for(int i=1;i<=3000;i++){
m[i][0]=1;
for(int j=1;j<=3000;j++){
m[i][j]=min(10000,m[i][j-1]*i);
}
}
}
void dfs(int cur,int num,int mul,int sum,ll ans){
if(cur==n+1){
if(mul==sum && num==n) res=(res+ans)%mod;
return ;
}
if(m[cur][n-num]*mul>limit) return ;
int x=1,maxx=0;
if(cur==1) maxx=max(0,n-12);
for(int i=maxx;i<=n-num;++i){
dfs(cur+1,num+i,mul,sum+i*cur,ans*inv[i]%mod);
mul*=cur;
}
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--){
res=0;
scanf("%d",&n);
limit=n*2;
dfs(1,0,1,0,fac[n]);
printf("%lld\n",res);
}
return 0;
}

E.Counting Sequences II

F.Rhyme scheme

题目大意为:给你两个数$n,k$ ,求长为$n$的大写字母字符串的第$k$个排列,$k$为$n$的贝尔数,详见贝尔数 。(这些字母排列的方式并未给出,经过观察后才能得出规律为:第$i$个位置上字母不能大于前面最大的字母加一,因此只能由AAB,不能有AAC)。

当时并没有看这个题,后来才补了这个题。

这个题用动态规划可写。定义$dp[i][j][k]$表示第$i$个位置(位置从高到低)前面出现过的最大的字母是$j$的情况下,第$i$位选$[‘A’,’A’+k]$的方案数总和。然后我们就可以利用一个循环去找到每一个位置上对应的字母。状态转移方程为(分两步):
step1: 求第$i$位选$’A’+k$的方案数
$$
dp[i][j][k]=\sum_{x=1}^{max(j,k)+1}dp[i-1][max(j,k)][x]
$$
step2:求前缀和
$$
dp[i][j][k]=\sum_{x=1}^{x=k}dp[i][j][x]
$$
由于数字过于庞大,因此我们需要使用__int128去处理数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+10;
const ll mod=998244353;
__int128 dp[30][30][30];
__int128 K;
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
void init(){
for(int j=0;j<=26;j++){
for(int k=1;k<=min(j+1,26);k++){
dp[1][j][k]=1;
}
}
for(int i=2;i<=26;i++){
for(int j=0;j<=26;j++){
for(int k=1;k<=min(j+1,26);k++){
for(int l=1;l<=min(26,max(j+1,k+1));l++){
dp[i][j][k]+=dp[i-1][max(j,k)][l];
}
}
}
}
for(int i=1;i<=26;i++){
for(int j=1;j<=26;j++){
for(int k=1;k<=min(26,j+1);k++){
dp[i][j][k]+=dp[i][j][k-1];
// write(dp[i][j][k]);
// printf(" ");
}
// printf("\n");
}
// printf("\n");
}
}
int main()
{
init();
int T,n;
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d",&n);
K=read();
K--;
printf("Case #%d: ",t);
int cur=0;
printf("A");
for(int i=n-1;i>=1;i--){
for(int j=min(cur+1,26);j>=0;j--){
if(dp[i][cur][j]<=K){
printf("%c",'A'+j);
K-=dp[i][cur][j];
cur=max(cur,j+1);
break;
}
}
}
printf("\n");
}
return 0;
}

G.Substring

H.Luhhy’s Matrix

I.Debug

J.Stone game

题目大意为:给你$n$个石头,每个石头都有一个重量。让你将石头分成两堆,使得第一堆的重量和大于等于第二堆的重量和,并且从第一堆任意取出一块石头后,第一堆的重量和小于等于第二堆的重量和。问总共有多少种分配方案。

其实就是一个背包问题,首先我们从题意中可以看出,第一堆每个石头的重量一定大于等于两堆石头的差,然后我们从大到小枚举差值(差值不会超过500),然后按照背包的方式去求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 500;
const int mod = 1e9+7;
ll a[N];
ll dp[160000];
bool cmp(ll x,ll y){
return x>=y;
}
int main(){
int T;scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
}
sort(a+1,a+n+1,cmp);
ll ans=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++){//枚举最小值
for(int j=sum;j>=a[i];j--){
dp[j]+=dp[j-a[i]];//当前sum
dp[j]%=mod;
//cout<<j<<' '<<dp[j]<<endl;
ll now=j;ll ano=sum-j;
if(now>=ano&&now-a[i]<=ano){
ans+=dp[j-a[i]];
ans%=mod;
}
}
}
printf("%lld\n",ans);
}
return 0;
}

K.Peekaboo

题目大意为:给你三个值$a,b,c$,表示原点到$Kblack$ ,原点到$CLS(NB!!)$,$Kblack$到$CSL$的距离,且两个人都在二维坐标系的整点上,问总共有多少种方案使得他们之间的距离关系成立。

求出圆$x^2+y^2=a^2$ 和 $x^2+y^2=b^2$ 上的整点,然后直接循环判断即可。具体求解方法参见圆上整点个数及坐标求解方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
ll d[4][2]={1,1,1,-1,-1,1,-1,-1};
set<pll>st[2];
void divide(ll r,ll exp,ll flag){//exp代表扩大多少倍
for(ll i=1;i*i<r;i++)
{
ll x=(ll)sqrt(r-i*i);
if(x*x+i*i==r && x!=i)
{
//负数域运算(x+i)*(x+i)
ll a=abs(x*x-i*i),b=2*x*i;
//八个对称的点
for(int j=0;j<4;j++) st[flag].insert({d[j][0]*a*exp,d[j][1]*b*exp});
for(int j=0;j<4;j++) st[flag].insert({d[j][0]*b*exp,d[j][1]*a*exp});
}
}
}
void solve(ll r,ll flag){
st[flag].clear();
//四个数轴上的点
st[flag].insert({r,0ll});st[flag].insert({-r,0ll});
st[flag].insert({0ll,r});st[flag].insert({0ll,-r});

for(ll i=2;i*i<=r;i++){
if(r%i==0){
divide(i,r/i,flag);
divide(r/i,i,flag);
}
}
}
bool len(pll x,pll y,ll c){
return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second)==c*c;
}
int main()
{
ll a,b,c,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld %lld %lld",&a,&b,&c);
solve(a,0);
solve(b,1);
int sum=0;
for(set<pll>::iterator it1=st[0].begin();it1!=st[0].end();it1++){
for(set<pll>::iterator it2=st[1].begin();it2!=st[1].end();it2++){
pii x=*it1,y=*it2;
if(len(x,y,c)) sum++;
}
}
printf("%d\n",sum);
for(set<pll>::iterator it1=st[0].begin();it1!=st[0].end();it1++){
for(set<pll>::iterator it2=st[1].begin();it2!=st[1].end();it2++){
pii x=*it1,y=*it2;
if(len(x,y,c)) printf("%d %d %d %d\n",x.first,x.second,y.first,y.second);
}
}
}
return 0;
}

I.Digit sum

签到题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
ll sum[11][N];
void init(){
memset(sum,0,sizeof(sum));
rep(b,2,10){
sum[b][1]=1;
}
rep(i,2,1000000){
rep(b,2,10){
ll now=i;
ll x=0;
while(now){
x+=now%b;
now/=b;
}
sum[b][i]=sum[b][i-1]+x;
}
}
}
int n,b;
int main(){
init();
int cas=1;
int T;scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&b);
printf("Case #%d: %lld\n",cas++,sum[b][n]);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------