近日补题
最近量很少啊，都不敢打比赛了
1033C|1600|DP
这题的有序性（无后效性）体现在a只能不断增加，当前阶段的a的值能表出之前所有a的范围。排序后从后向前dp即可，注意排序后index乱了，我们每步操作需要判断随机index的必胜必败（dp结果是每个数是必胜必败，根据基本博弈知识即可），不能顺序遍历，所以用map存即可，注意不存在（未出现和必败要区分,因为未出现体现的是a的大小，而不是index）
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
| struct ui{int fir;int sec;bool operator<(const ui b)const{return this->fir<b.fir;}};
const int maxn=1e5+10;
ui in[maxn];
int dp[maxn];
int tmp;
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;++i)dp[i]=0;
map<int ,int> ma;
for(int i=1;i<=n;++i){
cin>>tmp;
in[i]={tmp,i};
}
sort(in+1,in+n+1);
for(int i=n;i>0;--i){
int tmp=1;
int tag=0;
while(1){
if(in[i].sec+tmp*in[i].fir>n)break;
else{
if(ma[in[i].sec+tmp*in[i].fir]==2){
tag=1;
}
}
tmp++;
}
tmp=1;
while(1){
if(in[i].sec-tmp*in[i].fir<1)break;
else{
if(ma[in[i].sec-tmp*in[i].fir]==2){
tag=1;
}
}
tmp++;
}
if(tag)dp[in[i].sec]=1;
else dp[in[i].sec]=2;
ma[in[i].sec]=dp[in[i].sec];
}
for(int i=1;i<=n;++i){
if(dp[i]==1)cout<<"A";
else cout<<"B";
}cout<<endl;
}
|
888D|1600|数学
k只有4，找规律，比如k为4时，就是恰好4个加恰3加恰2,求出恰好的值即可，这个恰好，可以用容斥（但我没推出来），也可以直接看每种个数有几个排列。
注意组合数很大(爆int)且不模时，不能用费马小定理（需要找一个足够大质数）。
k为3和4时需要找出恰3、4的个数（可以直接枚举），能造成全不一样的只有两种，轮换和两两交换，其中3只有轮换，3-1=2；4也有轮换，不过是6个（可以用树型遍历出来），交换为4-1=3，共9个。
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
| const ll N=2500;
ll C[N][N],n,a,b;
void init(){
for(ll i=0;i<N;++i){
for(ll j=0;j<=i;j++){
if(j==0)
C[i][j]=1;
else{
C[i][j]=(C[i-1][j-1]+C[i-1][j]);
}
}
}
}
ll A[2000];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
ll n,k;cin>>n>>k;
init();
A[1]=1;
for(ll i=2;i<1005;++i){
A[i]=A[i-1]*i;
}
if(k==1){
cout<<1<<endl;
return 0;
}else if(k==2){
cout<<C[n][2]+1<<endl;
}else if(k==3){
cout<<C[n][3]*2+C[n][2]+1<<endl;
}else{
cout<<C[n][4]*9+C[n][3]*2+C[n][2]+1<<endl;
}
}
|
1032C|1700|dp
他不断向后走，且只用管最后一位手指，满足无后效性；步步可行即可行，满足最优化原理。
dp需要2个变量，第i位，是从前一位的第几个手指而来。
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
| const int maxn = 2e5+10;
int in[maxn];
int dp[maxn][6];
int main(){
int n;cin>>n;
for(int i=1;i<=n;++i){
cin>>in[i];
}
for(int i=1;i<=5;++i){
dp[1][i]=1;
}
for(int i=2;i<=n;++i){
if(in[i-1]==in[i]){
for(int j=1;j<=5;++j){
for(int k=1;k<=5;++k){
if(j!=k&&dp[i-1][j]!=0){
dp[i][k]=j;
}
}
}
}else if(in[i-1]<in[i]){
for(int j=1;j<=5;++j){
if(dp[i-1][j]!=0){
for(int k=j+1;k<=5;++k){
dp[i][k]=j;
}
}
}
}else{
for(int j=1;j<=5;++j){
if(dp[i-1][j]!=0){
for(int k=1;k<j;++k){
dp[i][k]=j;
}
}
}
}
}
int tag=0,pos=-1;
for(int i=1;i<=5;++i){
if(dp[n][i]){
tag=1;pos=i;
break;
}
}
if(tag==0){
cout<<-1<<endl;
}else{
stack<int> stk;
stk.push(pos);
for(int i=n;i>1;--i){
stk.push(dp[i][pos]);
pos=dp[i][pos];
}
while(stk.size()){
cout<<stk.top()<<' ';
stk.pop();
}
cout<<endl;
}
}
|
835c|1600|区间dp
简单的区间dp，每个区间存初始亮度为0…c的个数，最后求出区间内各自个数再统计即可。
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
| const int maxn=1005;
int dp[105][105][11];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
int n,q,c;cin>>n>>q>>c;
int x,y,s;
for(int i=1;i<=n;++i){
cin>>x>>y>>s;
dp[x][y][s]++;
}
for(int i=1;i<=100;++i){
for(int j=1;j<=100;++j){
for(int k=0;k<=c;++k){
dp[i][j][k]+=dp[i-1][j][k];
dp[i][j][k]+=dp[i][j-1][k];
dp[i][j][k]-=dp[i-1][j-1][k];
}
}
}
int t,x1,y1,x2,y2;
while(q--){
cin>>t>>x1>>y1>>x2>>y2;
int tmp[11];
for(int i=0;i<=c;++i){
tmp[i]=dp[x2][y2][i]-dp[x1-1][y2][i]-dp[x2][y1-1][i]+dp[x1-1][y1-1][i];
}
int ans=0;
for(int i=0;i<=c;++i){
ans+=tmp[i]*((t+i)%(c+1));
}
cout<<ans<<endl;
}
}
|
1061c|1700|dp
维护当前数是第几个，即可满足无后效性。
看复杂度，1e5*sqrt（1e6），再看time limit：3s，刚好。
cnt中存能排在i位的数现在出现了几个。一个数排如果可以排第i个，则答案增加cnt[i-1];
实现是：遍历过程实时加答案，计算答案时不能考虑自己，所以计算完答案后再遍历一次更新cnt。
更新cnt时，同样注意不能影响自己 ，所以要从大因子开始，为了变为sqrt的复杂度，先从1到sqrt，取其和a[i]除的结果更新；然后从sqrt到1，更新。
注意，此类优化方法，虽然把复杂读降为sqrt，产生的因子还是n的，不能开sqrt的cnt！！！！（re8发）
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
| const int maxn=1e5+100;
ll a[maxn];
ll cnt[1000000];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
ll ans=0;
cnt[0]=1;
for(ll i=1;i<=n;++i){
ll tmp=sqrt(a[i]);
for(ll j=1;j*j<=a[i];++j){
if(a[i]%j==0){
ans+=cnt[j-1]+cnt[(a[i]/j)-1];
if(j*j==a[i])ans-=cnt[j-1];
ans%=mod;
}
}
for(ll j=1;j*j<=a[i];++j){
if(a[i]%j==0){
if(j*j!=a[i])cnt[a[i]/j]+=cnt[(a[i]/j)-1];
cnt[a[i]/j]%=mod;
}
}
for(ll j=tmp;j>=1;--j){
if(a[i]%j==0){
cnt[j]+=cnt[j-1];
cnt[j]%=mod;
}
}
}
cout<<ans<<endl;
}
|