http://www.hzxjhs.com:83/contest/55
说实话这次比赛真的很水。。然而我只拿了140分，面壁反思。
第一题：
发现数位和sum最大就是9*18，k最大1000，那么sum*k最大不过2*10^5，若能被x整除，则x也不超过200000，暴力即可。
不知道学军OIlonglong用%I64d还是%lld输入，用了%I64d爆零。。改成lld就AC了。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7
8 typedef long long LL;
9
10 int main()
11 {
12 freopen("a.in","r",stdin);
13 freopen("a.out","w",stdout);
14 int T;
15 scanf("%d",&T);
16 while(T--)
17 {
18 LL l,r;
19 int k,ans=0;
20 scanf("%lld%lld%d",&l,&r,&k);
21 for(int i=1;i<=200000;i++)
22 {
23 if(i>r || i<l) continue;
24 int sum=0,x=i;
25 while(x)
26 {
27 sum+=x%10;
28 x/=10;
29 }
30 if((sum*k%i)==0) ans++;
31 }
32 printf("%d
",ans);
33 }
34 return 0;
35 }
第二题
原本用了矩阵乘法来表示i到j走2^k步有多少种方案，方案数>=1就建一条边，最后跑最短路。。超时，50分。
然后发现自己真的好傻逼。。
直接看代码吧。就是一个简单DP，c[i][j][k]表示i到j走2^k步是否可以，d[i][j]表示i到j最少时间。
if d[i][l][k-1]==1 && d[l][j][k-1]==1 --> d[i][j][k]=1
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7
8 typedef long long LL;
9 const int N=60,M=11000;
10 int n,m,d[N][N];
11 bool c[N][N][70];
12
13 int minn(int x,int y){return x<y ? x:y;}
14
15 int main()
16 {
17 freopen("a.in","r",stdin);
18 freopen("a.out","w",stdout);
19 scanf("%d%d",&n,&m);
20 memset(c,0,sizeof(c));
21 memset(d,63,sizeof(d));
22 for(int i=1;i<=m;i++)
23 {
24 int x,y;
25 scanf("%d%d",&x,&y);
26 d[x][y]=1;
27 c[x][y][0]=1;
28 }
29 for(int k=1;k<=64;k++)
30 for(int i=1;i<=n;i++)
31 for(int j=1;j<=n;j++)
32 for(int l=1;l<=n;l++)
33 {
34 if(c[i][l][k-1] && c[l][j][k-1])
35 {
36 d[i][j]=1;
37 c[i][j][k]=1;
38 }
39 }
40 for(int i=1;i<=n;i++)
41 for(int j=1;j<=n;j++)
42 for(int l=1;l<=n;l++)
43 {
44 d[i][j]=minn(d[i][j],d[i][l]+d[l][j]);
45 }
46 printf("%d
",d[1][n]);
47 return 0;
48 }
第三题
直接递归。
作死用了树状数组维护前缀和，用个数组就好了吧。。
用树状数组超时90分，改成数组就A了。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7
8 const int N=1100;
9 char s[N];
10 int n,c[N],d[N][N][2];
11
12 int lowbit(int x){return x&(-x);}
13 void add(int x,int d){
14 for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d;
15 }
16 int getsum(int x){
17 int ans=0;
18 for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];
19 return ans;
20 }
21
22 bool check(int l,int r,int tmp)
23 {
24 if(d[l][r][tmp]!=-1) return d[l][r][tmp];
25 if(l>r) return 0;
26 if((getsum(r)-getsum(l-1))&1) return d[l][r][tmp]=0;
27 if(tmp==0)
28 {
29 if(l==r && s[l]=='0') return d[l][r][tmp]=1;
30 if(s[l]=='1' && s[r]=='1' && check(l+1,r-1,1)) return d[l][r][tmp]=1;
31 return d[l][r][tmp]=0;
32 }
33 else
34 {
35 int t=getsum(l-1);
36 for(int i=l;i<r;i++)
37 {
38 if((getsum(i)-t)&1) {d[l][i][0]=d[i+1][r][0]=0;continue;}
39 if(check(l,i,0) && check(i+1,r,0)) return d[l][r][tmp]=1;
40 }
41 return d[l][r][tmp]=0;
42 }
43 }
44
45 int main()
46 {
47 freopen("a.in","r",stdin);
48 // freopen("a.out","w",stdout);
49 int T;
50 scanf("%d",&T);
51 while(T--)
52 {
53 scanf("%d",&n);
54 scanf("%s",s+1);
55 memset(c,0,sizeof(c));
56 memset(d,-1,sizeof(d));
57 for(int i=1;i<=n;i++)
58 if(s[i]=='1') add(i,1);
59 if(check(1,n,0)) printf("YES
");
60 else printf("NO
");
61 }
62 return 0;
63 }