（寒假训练赛，也是lj难得补完的一场
https://codeforces.com/contest/1005
A.题意是 每一个楼梯有x个台阶，小女孩爬楼的时候会从1开始数每层楼有几个台阶，现在给给出n个数字a1~an，代表着小女孩爬楼时数数的序列，求有多少层楼梯，并且输出每层楼梯台阶数。
解法：for循环模拟小女孩从1开始数，数到下一个1的话楼层++，然后把他前一个数存进去。
int now = 0;
for(int i = 0;i < n;++i){
cin>>a;
if(a == now+1)now++;
else if(a == 1){
ans[cnt++] = now;now = 1;
}
}
ans[cnt++] = now;
cout<<cnt<<endl;
for(int i = 0;i < cnt;++i)cout<<ans[i]<<" ";
B.题意是 给出两串序列，每次能对非空字符串的左端字符，用最少移动次数使得两个字符串相等（空串也相等
解法：从后往前对比两个字符串的最长后缀，然后计算出删除前端的字串长度
int l1 = s1.size(),l2= s2.size()，flag = 0;
for(int i = l1-1,j = l2-1;i>=0,j>=0;--i,--j){
if(s1[i]!=s2[j]){break;}
flag++;
}
cout<<l1+l2-flag*2<<endl;
C.定义：有一个数组，每个元素都能够找到另一个元素使得两个元素之和为2的幂。如果给出的数组不满足条件则删除部分元素或者全部元素(空集符合条件），求最少删除多少数可以满足定义
解法：这题比较灵性了，普通暴力肯定不行，一开始想的是用map映射2的幂，然后for查询依次判断和是否为2的幂，这个时候复杂度应该有n*n*logn（我也忘了最初思路是不是这样的，反正复杂度挺高的）。优化后的方法是这样，在录入数据的时候用map存一下每个元素的个数，然后根据数据范围得出幂的范围应该在1~31之间，于是依次枚举2的1次方..2的31次方，然后判断1~n个元素里有没有存在另一个元素使得他两的和等于此时的2的幂（假设为sum好了），这个时候不用挨个去遍历找了，直接用mp[sum-a[i]]来判断其对应元素是否存在就好啦，如果成功的话打个tag，下次遇见这个元素就知道它不用被删除了√。最后的最后是对打tag的地方处理一遍，没有标记的就是要删除的数~
坑点：如果数组元素中存在本身就是2的几次幂的数，需要判断处理一下当sum-a[i]==a[i]时，如果mp[a[i]]==1则不能打tag，如果>=2的话才可以~
map<ll,int> mp,mmp,qwq;
int main(){
for(int i = 0;i < n;++i){
cin>>a[i]; qwq[a[i]]++;
}
if(n==1)return puts("1"),0;
sort(a,a+n);
for(int i = 1;i<= 31;++i){
sum<<=1;
if(sum>a[n-1]+a[n-2])break;
for(int j = 0;j <n;++j){
if(sum-a[j]<=0)break;
if(mp[a[j]])continue;
if(qwq[sum-a[j]]){
if((sum == (a[j]+a[j]))&&qwq[a[j]]>=2)mp[a[j]] = 1;
else if(sum != a[j]+a[j])mp[a[j]] = mp[sum-a[j]] = 1;
}
}
}
for(int i = 0;i < n;++i){if(!mp[a[i]])ans++;}
}
D.Polycarp喜欢被3整除的数字，给一个1~2*1e5位数的数字(直接当字符串看啦），在上面进行切割，切割后尽可能让多的区间的每部分的位数相加和为3的倍数，求出最多可以形成多少个这样的区间，不含前导零。
解法：d挺简单的其实，个人认为还没有c好玩（也可能是c这类遇上的比较少），就每个数对3取余只有0，1，2三个数，其中余数为0的是3的倍数，余数为1与余数为2的相加也是，三个余数为1或者三个余数为2的相加也是。所以就遇见余数为0的ans++，如果遇见1之后遇见了2也ans++然后统计的地方清零，先2后1同理........
cin>>s;int l = s.size();
int now = 0;int tp = 0;
for(int i = 0;i< l;++i){
if(s[i]=='0'||s[i]=='3'||s[i]=='9'||s[i]=='6'){
ans++;now = 0;tp = 0;
}
else if(s[i]=='2'||s[i]=='5'||s[i]=='8'){
if(now==0)now =1,tp++;
else if(now==2)ans++,now = 0,tp = 0;
else if(now==1){
tp++;if(tp==3)ans++,now = 0,tp = 0;
}
}
else if(s[i]=='1'||s[i]=='4'||s[i]=='7'){
if(now==0)now = 2,tp++;
else if(now==1)ans++,now = 0,tp = 0;
else if(now==2){
tp++;if(tp==3)ans++,now = 0,tp = 0;
}
}
}
cout<<ans<<endl;
从这题开始以后基本上是自闭补题了，打了一年div3还不能稳定4题，还是练的太少了+不够认真。（碎碎念（蒟蒻反思自己
（被学弟打爆，然后还老挨骂，暴哭（反向奶——抱着lj这学期肯定进不了实验室qwq也没机会出去打比赛的心态好好学
E1.给出整数n和m，还有p1~pn的排列，排列中1~n恰好出现一次。定义：中位数是位于非降序排序后序列的中间，如果序列长度为偶数，则使用两个中间元素的左侧。求有多少区间的中位数为m
解法：根据题目给出的条件可以知道，只有包含m的区间才可能以m为中位数。然后仔细想想，m的位置只和比它大还有比它小的数有关，于是从m的位置往左往右走一遍，遇见比m大的+1，小的则-1，用两个数组维护一下x，统计出每个值出现次数，然后当两个区间的和加起来为0或者为1的时候m为组合区间的中位数
cin>>n>>m;
for(int i = 1;i <= n;++i){
cin>>a[i];if(a[i]==m)tp = i;
}
sum[tp] = 0;mmp[0]++;mp[0]++;//这个地方注意x m的单区间左右都放放
for(int i = tp-1;i >0;--i){
if(a[i]>m)sum[i] = sum[i+1]+1;
else if(a[i]<m)sum[i] = sum[i+1]-1;
else sum[i] = sum[i+1];
mp[sum[i]]++;
}
for(int i = tp+1;i <=n;++i){
if(a[i]>m)sum[i] = sum[i-1]+1;
else if(a[i]<m)sum[i] = sum[i-1]-1;
else sum[i] = sum[i-1];
mmp[sum[i]]++;
}
int cnt;ll ans = 0;
if(mp.size() < mmp.size()){//感觉这里不用大小比较优化似乎也行？
for(iter1 = mp.begin();iter1!=mp.end();iter1++){
cnt = iter1->first;cnt*=(-1);
ans+=( mmp[cnt] * iter1->second);
ans+=(mmp[cnt+1] * iter1->second);
}
}
else {
for(iter1 = mmp.begin();iter1!=mmp.end();iter1++){
cnt = iter1->first;cnt*=(-1);
ans+=( mp[cnt] * iter1->second);
ans+=(mp[cnt+1] * iter1->second);
}
}
cout<<ans<<endl;
E2.定义和E1差不多 就是给出的排列不一定是1~n只出现一次。
解法：在别人的博客上学的，求中位数刚好为m的情况在此时可能有点复杂，但是可以通过求中位数大于等于m的区间数减去中位数大于等于m+1的区间数得到答案。
那么该怎么求中位数大于等于m的区间数，根据定义知道，当该区间>=m的数大于<m的数，那么此时区间的中位数大于等于m。
//终于理解清思路了
也是用+-1来维护区间内大于m和小于m的数的多少，要求[a,b]这个区间是大于0还是小于0可以用[1,b]-[1,a-1]得到。（前缀和思想）
为了防止下标为负数的数组越界问题，我们开两倍数组ape[2*N]用来存储某个值出现的次数，cnt初始化为n，用于维护1~i的前缀和。sum用来维护在[1,i-1]处有多少个值小于当前cnt（这样就可以知道以i为右端点的区间，有多少个是大于0的了）。然后枚举右端点，当我们加入一个大于等于m的端点时，就有sum+ape[cnt]个端点可以和该端点匹配，cnt++;小于m时，cnt--,sum-=ape[cnt]。最后累加得解
//好艰难地理清了表述，可能后期有了更好的理解会更新表述吧。
int a[N],ape[2*N],n;
ll sv(int m){
mem(ape, 0);
int cnt = n;ape[cnt]++;
ll sum = 0,ans = 0;
for(int i = 0;i < n;++i){
if(a[i] >= m){
sum+=ape[cnt];cnt++;
}
else {
cnt--;sum-= ape[cnt];
}
ape[cnt]++;ans+=sum;
}
return ans;
}
int main(){
int m;ll ans;
cin>>n>>m;
for(int i = 0;i < n;++i)cin>>a[i];
ans = sv(m)-sv(m+1);
cout<<ans<<endl;
}
https://codeforces.com/contest/1005/problem/F
F.最短路树，给n个点和m条边，首都编号为1,设di为首都到第i个城市要走的路，最小化（d2+...+dn)，有多个方案则输出多个方案，以01串的方式（选取该条边则1），若方案大于k则输出k个。
解法：bfs找到所有方案，dfs输出结果
1 int n,m,k,dis[N],u,v;
2 char s[N];bool vis[N];
3 vector<pii>g[N];
4 vector<int>pre[N];
5 vector<string>res;
6 void bfs(){
7 pii tp;queue< pii > q;int v;
8 dis[1] = 0;vis[1] = true;
9 q.push({1,0});
10 while(!q.empty()){
11 tp = q.front();q.pop();
12 for(int i = 0;i < g[tp.fi].size();++i){
13 v = g[tp.fi][i].fi;
14 if(!vis[v]){
15 vis[v] = true;
16 dis[v] = tp.se + 1;
17 q.push({v,dis[v]});
18 }
19 }
20 }
21 }
22 void dfs(int u){
23 if(res.size() >= k)return ;
24 if(u > n){
25 res.pb(s+1);return;
26 }
27 for(int i = 0;i < pre[u].size();++i){
28 s[pre[u][i]] = '1';
29 dfs(u+1);
30 s[pre[u][i]] = '0';
31 }
32 }
33 int main(){
34 fio
35 cin>>n>>m>>k;
36 for(int i = 1;i <= m;++i){
37 cin>>u>>v;
38 g[u].pb({v,i}),g[v].pb({u,i});
39 }
40 bfs();
41 pii p;
42 for(int i = 2; i <= n;++i){
43 for(int j = 0;j < g[i].size();++j){
44 p = g[i][j];
45 if(dis[p.fi]+1 == dis[i]) pre[i].pb(p.se);
46 }
47 }
48 for(int i = 1;i <= m;++i)s[i] = '0';
49 dfs(2);
50 cout<<res.size()<<endl;
51 for (int i = 0; i < res.size(); i++) cout << res[i] << endl;
52 return 0;
53 }