比赛时因为一些情况分心了，导致后面写的很慌，心态不好，唉
C . 模拟
链接：https://codeforces.com/contest/1191/problem/C
一个类似于栈的容器，有m个元素可删，每次可以删除最右边k个元素中可删的，其他元素随之移动，问删完m个元素要几次操作
A:
1.只要模拟他说的过程就行了
开始时想的： 记录每个需删除元素的所属块（a/k），和块中序号（a%k）
然后遍历，当所属块与当前处理块now不同时删除一次，ans++ ，并对后面的元素的块和块中序号进行更新
两重循环，所以是n^2复杂度
写时出现的错误： 1），假如要删除n次，只会出现n-1次不同，所以最后ans要增加1
2），元素是从1开始的，假如k=5 ，有1，2，3，4，5要划分为一块，但（1，2，3，4）/k=0 ，5/k=1 ，所以要处理一下让元素从0开始
3），每次更新时前移数量div要归零，否则多次重复更新会重复删除很多次div
debug了许多次，写成这个亚子：
#include <bits/stdc++.h>
#define rep(i ,x ,y) for( int i=x ;i<=y ;i++)
using namespace std;
typedef long long ll;
ll n ,m ,k ,ans=1; // 1）ans要+1
struct Op{
ll a,n,res;
}op[100500];
int main( ){
scanf("%lld%lld%lld" ,&n ,&m ,&k);
rep( i ,1 ,m ){
scanf("%lld" ,&op[i].a );
op[i].a--; // 2）处理使元素从零开始
op[i].n = op[i].a/k;
op[i].res = op[i].a%k;
}
ll div = 0 ,now = op[1].n ,d ,tmp=0;
rep( i ,1 ,m ){
if( op[i].n == now ){
tmp++;
}
else{
div+=tmp; //3）及时更新div
rep( j ,i ,m){
if( op[j].res<div ){
op[j].n -= div/k;
d = div%k;
op[j].res -= d;
if( op[j].res<0 ){
op[j].n--;
op[j].res += k;
}
}
else op[j].res -= div;
}
ans++;
tmp = 1;
div = 0; //3）及时更新div
now = op[i].n;
}
}
printf("%lld" ,ans);
return 0;
}
结果：
emm，果然更新操作太耗时了
2. 写超时的主要原因是div的更新太草了，每个元素更新一次就够了，这样把一次的更新分成了许多次，达到了n^2复杂度
还有就是没有完全利用题目已知信息，不限于此题，这些可利用已知信息有：
1）已知的或天然的序（按递增，递减给出的数值，时间序……
2）已知的索引与值的关系（函数，映射
3）已知的值与值之间的关系
4）已知的数据范围
做题时不要急于写代码，应该先注意是否将已知的信息完全利用，可以减少很多写代码的时间（就像高中做数学时要多读几遍题目，发现陷阱
越是简单题越要注意
这题m个可删元素是按递增顺序给出的，这就是说其下标的大小就是 再次元素之前 已经删除了多少个元素
利用这条信息，每个元素的更新只于当前div有关，所以只用更新一次，其他思路不变，on 时间复杂度之内就能完成
#include <bits/stdc++.h> #define rep(i ,x ,y) for( int i=x ;i<=y ;i++) using namespace std; typedef long long ll; ll m ,n ,k; ll a[100500]; int main( ){ scanf("%lld%lld%lld" ,&n ,&m ,&k); rep( i , 1 ,m )scanf("%lld" ,&a[i]) ,a[i]--; ll div = 0 ,now ,ans =1 ; now = a[1]/k; rep( i , 2 ,m){ if( (a[i]-div)/k != now ){ ans++; div = i-1; //已删元素个数 now = (a[i]-div)/k; //当前判断块 } } printf("%lld" ,ans); return 0; }
D. 有特判的贪心
Q：有n堆石子，每次操作可从任意一堆数量大于0的堆中取出一个，两人轮流操作，当某方操作后出现以下情况：
1. 所有堆都为0
2. 有两个堆石子数量相同
时 ，该方失败，问最后成功的是哪一方
A：
1. 比赛时乱搞，推断除特殊情况外，先手必胜，明显是错的
2. 题目中每个人每次只能改变一堆的一个棋子，对对方的影响十分有限，所以只要保证自己不会输的情况下贪心的取就好
贪心策略：排序，每次都取最少堆的，因为这样不会重复，为避免重复，排序后第1堆取到0 ，第2堆取到1 ，第三堆取到2 ，3 ， 4 ，5……以此类推，直到不能再取时就能确定输方了
要注意开局就会出现输赢的几种特判 ：
1）有3堆及以上石子数量相同
2）有多个2堆数量相同的组合
3）破坏了一个2堆相同一定会出现另一个2堆相同
4）开局就没法再取了
特判后贪心模拟再判奇偶即可
#include <bits/stdc++.h> #define rep(i ,x ,y) for( int i=x ;i<=y ;i++) using namespace std; typedef long long ll; map <int ,int> mp; int n ,a[150000]; int main( ){ scanf("%d" ,&n ); rep( i ,1 ,n ){ scanf("%d" ,&a[i] ); mp[ a[i] ] ++; } sort( a+1 ,a+n+1 ); //特判 int flag=0 ,mp2=-1 ,mp2i; rep( i ,1 ,n ){ if( mp[ a[i] ] >= 3 ){ flag = 1; break; } if( mp[ a[i] ] == 2){ if( mp2 >= 0 && a[i] != mp2){ flag = 1; break; } mp2 = a[i]; mp2i=i; if( mp2 == 0 || mp[mp2-1]>0){ flag = 1; break; } } } if( flag ){ printf("cslnb"); return 0; } ll turn = 0 ,now = 0; //常规判断 if( mp2 >0 ){ mp[ mp2 ]--; mp[ mp2-1 ]++; a[ mp2i ]--; turn++; } sort( a+1 ,a+1+n ); rep( i ,1 ,n ){ turn += a[i]-now; now++; } if( turn&1 )printf("sjfnb"); else printf("cslnb"); return 0; }
3.发现了一种很奇妙的代码写法：
return printf("XXXX") , 0;
感觉这样写不太好，不过做题时用用也无妨
E. 贪心模拟，前缀和
给一个长为n的01串，每次操作可以将长为k的连续子串全变为1或0，两个人轮流操作，谁先将串全变为1或0，谁就赢
问最后谁会赢，或两人都不会赢
1. 又发现了一种奇妙写法
scanf("%1d" ,&a[i]);
每次只读入长度唯一的数字，可以将数字字符串直接读到数组里面去v
2. 首先，利用前缀和判断第一个人可不可以一击制胜，如果不行， 就一定是第二个人胜 或 都不胜 ，因为第二个人可以干扰其使其不能取胜
然后利用前缀和判断第二个人可不可以一击制胜，如果不行，与之前同理，就都不胜
判断第一个人暴力一遍就行
判断第二个人要判断k与n/2的关系
如果k<n/2 ,他就有够不到的地方，所以不能去取胜
k>=n/2，关键判断取最左右后互不交叉的两部分
如果其中一部分全是1且另一部分全是0 ，就能保证一击取胜，否则由于第一个人的干扰，总有不能取胜的情况发生
#include <bits/stdc++.h> #define rep(i ,x ,y) for( int i=x ;i<=y ;i++) using namespace std; typedef long long ll; int n ,k ,a[100050] ,sum[100050]; int main( ){ scanf("%d%d" ,&n ,&k); rep( i ,1 ,n ){ scanf("%1d" ,&a[i]); sum[i] = sum[i-1]+a[i]; } rep( i ,1 ,n-k+1 ){ if( sum[i-1]+ (sum[n]-sum[i+k-1]) == 0 ) return printf("tokitsukaze") , 0; if( sum[i-1]+ (sum[n]-sum[i+k-1]) == n-k ) return printf("tokitsukaze") , 0; } if( k*2 < n)return printf("once again") , 0; int l = n-k-1; if( sum[l] == l && sum[n]-sum[n-l]==0 ) return printf("quailty") , 0; if( sum[l] == 0 && sum[n]-sum[n-l]==l ) return printf("quailty") , 0; return printf("once again") , 0; }
或者暴力模拟前两步的所有操作应该也可以
F 感觉是有技巧的暴力，有思路没写的能力，先学今天的单调栈而不补此题