http://codeforces.com/problemset/problem/182/D 用均摊 \(N*logN\) 的做法，可以把字符串尽可能的压缩 大致把字符串 \(s\) 压缩成 \(N*T\) 的模式（\(N\)为数字，\(T\)为字符串） 然后求一下两个 \(N\) 的公因数个数就可以了 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
using namespace std;
string a,b;
string s;
string t;
string pa,pb;
int ta,tb;
int ans;
int main()
{
cin>>a>>b;
for(int i=1;i<=a.size();i++)
{
if(a.size()%i==0)
{
s=a.substr(0,i);
bool bj=0;
for(int j=i;j<a.size();j+=i)
{
t=a.substr(j,i);
if(t!=s)
{
bj=1;
break;
}
}
if(bj==0)
{
pa=s;
break;
}
}
}
for(int i=1;i<=b.size();i++)
{
if(b.size()%i==0)
{
s=b.substr(0,i);
bool bj=0;
for(int j=i;j<b.size();j+=i)
{
t=b.substr(j,i);
if(t!=s)
{
bj=1;
break;
}
}
if(bj==0)
{
pb=s;
break;
}
}
}
if(pa!=pb)
{
cout<<0;
return 0;
}
ta=a.size()/pa.size();
tb=b.size()/pb.size();
for(int i=1;i<=min(ta,tb);i++)
{
if(ta%i==0&&tb%i==0) ans++;
}
cout<<ans;
return 0;
}
http://codeforces.com/problemset/problem/231/D 题目还是比较简单，就是几何判断一下就行 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int x,y,z;
int x1,y1,z1;
int a1,a2,a3,a4,a5,a6;
int ans;
int main()
{
cin>>x>>y>>z;
cin>>x1>>y1>>z1;
cin>>a1>>a2>>a3>>a4>>a5>>a6;
if(y<0) ans+=a1;
if(z<0) ans+=a3;
if(x<0) ans+=a5;
if(y>y1) ans+=a2;
if(z>z1) ans+=a4;
if(x>x1) ans+=a6;
cout<<ans;
return 0;
}
http://codeforces.com/problemset/problem/264/B \(D_i\) 代表最后一个数含有质因子 \(i\) 的good sequence长度 然后状态转移就是求出每一个 \(a_i\) 的质因子，然后找到最大的 \(D_j\) ，对每个质因子进行更新。 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
using namespace std;
int n;
int a[100010]={};
int d[100010]={};
int ans;
int p;
int t;
queue<int> q;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
p=sqrt(a[i]);
t=0;
for(int j=2;j<=p;j++)
{
if(a[i]%j==0)
{
q.push(j);
t=max(d[j],t);
}
while(a[i]%j==0)
{
a[i]/=j;
}
}
if(a[i]!=1)
{
q.push(a[i]);
t=max(t,d[a[i]]);
}
while(!q.empty())
{
p=q.front();
q.pop();
d[p]=max(t+1,d[p]);
}
}
if(n==1&&a[1]==1) ans=1;
for(int i=2;i<=100000;i++)
{
ans=max(ans,d[i]);
}
cout<<ans;
return 0;
}
http://codeforces.com/problemset/problem/126/B 就是用kmp的方法，构建一个前缀指针数组 然后找一下中间有没有就行了，如果没有，就把前缀数组指针向前移一下。 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
using namespace std;
string s;
int p[1000010]={};
char b[1000010]={};
int t;
map<int,bool> ha;
int main()
{
cin>>s;
for(int i=1;i<=s.size();i++) b[i]=s[i-1];
p[1]=0;
int j=0;
for(int i=2;i<=s.size();i++)
{
while((j>0)&&(b[j+1]!=b[i])) j=p[j];
if(b[j+1]==b[i]) j++;
p[i]=j;
}
for(int i=2;i<s.size();i++)
{
ha[p[i]]=1;
}
t=p[s.size()];
ha[0]=1;
while(ha[t]==0)
{
t=p[t];
}
if(t==0)
{
cout<<"Just a legend";
return 0;
}
cout<<s.substr(0,t);
return 0;
}
http://codeforces.com/problemset/problem/295/B 倒着做一遍floyd就可以了 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
using namespace std;
long long n;
long long a[510][510]={};
long long x[510]={};
long long d[510][510]={};
bool p[510]={};
long long ans;
stack<long long> u;
int main()
{
scanf("%I64d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%I64d",&a[i][j]);
d[i][j]=a[i][j];
}
}
for(int i=1;i<=n;i++) scanf("%I64d",&x[i]);
for(int i=n;i>=1;i--)
{
for(int j=1;j<=n;j++)
{
if(p[j]==1)
for(int k=1;k<=n;k++)
{
if(p[k]==1)
{
d[j][x[i]]=min(d[j][x[i]],d[j][k]+d[k][x[i]]);
d[x[i]][j]=min(d[x[i]][j],d[x[i]][k]+d[k][j]);
}
}
}
p[x[i]]=1;
ans=0;
for(int j=1;j<=n;j++)
{
if(p[j]==1)
for(int k=1;k<=n;k++)
{
if(p[k]==1)
{
d[j][k]=min(d[j][k],d[j][x[i]]+d[x[i]][k]);
ans+=d[j][k];
}
}
}
u.push(ans);
}
while(!u.empty())
{
printf("%I64d ",u.top());
u.pop();
}
return 0;
}