http://codeforces.com/contest/111/problem/B 为什么自己总是这么智障...明明这题很简单啊... 就是记录一下每个因子最后出现的位置就行 这题我开始主要卡在总想知道因子出现了多少次？没有充分利用题目特点？ 我觉得卡题的主要原因就是因为智障...
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
| #include<bits/stdc++.h>
using namespace std;
int p[100010]={};
int n;
int x[100010]={};
int y[100010]={};
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
for(int i=1;i<=n;i++)
{
int t;
int ans=0;
for(int j=1;j*j<=x[i];j++)
{
if(x[i]%j==0)
{
if(p[j]<i-y[i])
{
ans++;
}
if(p[x[i]/j]<i-y[i]&&j*j!=x[i])
{
ans++;
}
p[j]=i;
p[x[i]/j]=i;
}
}
printf("%d\n",ans);
}
return 0;
}
|
http://codeforces.com/problemset/problem/494/B \(a_i\) 代表结尾最后一个数小于等于 i 的情况总数 先用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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
string hs,ht;
char s[100010]={};
char t[100010]={};
int p[100010]={};
bool q[100010]={};
long long a[100010]={};
long long sum=0;
long long pp;
int main()
{
cin>>hs>>ht;
for(int i=0;i<hs.size();i++)
{
s[i+1]=hs[i];
}
for(int i=0;i<ht.size();i++)
{
t[i+1]=ht[i];
}
p[1]=0;
int j=0;
for(int i=2;i<=ht.size();i++)
{
while((j>0)&&t[j+1]!=t[i]) j=p[j];
if(t[j+1]==t[i]) j++;
p[i]=j;
}
j=0;
for(int i=1;i<=hs.size();i++)
{
while(j>0&&t[j+1]!=s[i]) j=p[j];
if(t[j+1]==s[i]) j++;
if(j==ht.size())
{
q[i]=1;
j=p[j];
}
}
for(int i=1;i<=ht.size();i++)
{
a[i-1]=1;
}
for(int i=ht.size();i<=hs.size();i++)
{
sum+=a[i-ht.size()];
sum%=mod;
if(q[i]==1) pp=sum;
a[i]=a[i-1]+pp;
a[i]%=mod;
}
a[hs.size()]--;
if(a[hs.size()]<0) a[hs.size()]+=mod;
cout<<a[hs.size()];
return 0;
}
|
http://codeforces.com/problemset/problem/400/D 先做一下并查集，再做一下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
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
| #include<bits/stdc++.h>
using namespace std;
int n,m,k;
int u,v,x;
vector<int> e[100010];
vector<int> c[100010];
int fa[100010]={};
int z[100010]={};
int l,r;
int ff(int x)
{
if(fa[x]==x) return x;
fa[x]=ff(fa[x]);
return fa[x];
}
int ans[510][510]={};
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
int l=0;
for(int i=1;i<=k;i++)
{
scanf("%d",&r);
for(int j=l+1;j<=l+r;j++)
{
z[j]=i;
}
l+=r;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&x);
e[u].push_back(v);
e[v].push_back(u);
c[u].push_back(x);
c[v].push_back(x);
if(x==0)
{
fa[ff(u)]=ff(v);
}
}
l=0;
for(int i=1;i<=n;i++)
{
if(z[i]!=z[i-1])
{
l=ff(i);
}
else
{
if(ff(i)!=l)
{
printf("No\n");
return 0;
}
}
}
printf("Yes\n");
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
if(i!=j) ans[i][j]=1000000000;
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<e[i].size();j++)
{
ans[z[i]][z[e[i][j]]]=min(ans[z[i]][z[e[i][j]]],c[i][j]);
}
}
for(int p=1;p<=k;p++)
{
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
ans[i][j]=min(ans[i][p]+ans[p][j],ans[i][j]);
}
}
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
if(ans[i][j]!=1000000000) printf("%d ",ans[i][j]);
else printf("-1 ");
}
printf("\n");
}
return 0;
}
|
http://codeforces.com/problemset/problem/319/B 依然是并不是特别难的均摊算法。 l代表向右最多能杀到哪里 t代表杀到那里的时间 然后状态转移比较显然，不懂就看看程序吧,
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
| #include<bits/stdc++.h>
using namespace std;
int n;
int a[100010]={};
int l[100010]={};
int t[100010]={};
int ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--)
{
if(i==n||a[i]<=a[i+1])
{
l[i]=i;
t[i]=1;
}
else
{
int p;
p=i+1;
while(1)
{
if(p==n+1) break;
if(a[i]<=a[p]) break;
l[i]=l[p];
t[i]=max(t[i]+1,t[p]);
p=l[p]+1;
ans=max(ans,t[i]);
}
}
}
printf("%d",ans);
return 0;
}
|
http://codeforces.com/problemset/problem/321/B 动态规划即可
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
| #include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int a[110],b[110],d[110];
int an,bn;
int dp[110][110][110][2];
bool v[110][110][110][2]={};
int ans;
bool cmp(int x,int y)
{
return x<y;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s;
if(s=="ATK")
{
an++;
cin>>a[an];
}
else
{
bn++;
cin>>b[bn];
}
}
for(int i=1;i<=m;i++)
{
cin>>d[i];
}
sort(a+1,a+an+1,cmp);
sort(b+1,b+bn+1,cmp);
sort(d+1,d+m+1,cmp);
v[0][0][0][0]=1;
v[0][0][0][1]=1;
for(int i=0;i<=m;i++)
{
for(int u=0;u<=1;u++)
{
for(int j=0;j<=an;j++)
{
for(int k=0;k<=bn;k++)
{
if(v[i][j][k][u]==0) continue;
if(u==0) ans=max(dp[i][j][k][u],ans);
if(u==1&&j==an&&k==bn) ans=max(dp[i][j][k][u],ans);
dp[i+1][j][k][u]=max(dp[i+1][j][k][u],dp[i][j][k][u]);
if(j<an&&d[i+1]>=a[j+1])
{
dp[i+1][j+1][k][u]=max(dp[i+1][j+1][k][u],dp[i][j][k][u]+d[i+1]-a[j+1]);
v[i+1][j+1][k][u]=1;
}
if(k<bn&&d[i+1]>b[k+1])
{
dp[i+1][j][k+1][u]=max(dp[i+1][j][k+1][u],dp[i][j][k][u]);
v[i+1][j][k+1][u]=1;
}
if((j==an&&k==bn)||u==1)
{
dp[i+1][j][k][u]=max(dp[i+1][j][k][u],dp[i][j][k][u]+d[i+1]);
v[i+1][j][k][u]=1;
}
dp[i+1][j][k][u]=max(dp[i+1][j][k][u],dp[i][j][k][u]);
v[i+1][j][k][u]=1;
}
}
}
}
cout<<ans<<endl;
return 0;
}
|