网站首页设计制作教程,兰州建设网站的公司,电子商务网站开发的总结,企业网站备案好不好后天就是 I C P C ICPC ICPC杭州站了#xff0c;今天把之前做的 d i v 3 div3 div3题补一下#xff0c;打完这场杭州站这赛季除了 E C F i n a l EC\,\,Final ECFinal就结束了#xff0c;以后应该要多打 c f cf cf比赛练习保持手感#xff0c;争取下赛季冲一下金牌。 感觉这…后天就是 I C P C ICPC ICPC杭州站了今天把之前做的 d i v 3 div3 div3题补一下打完这场杭州站这赛季除了 E C F i n a l EC\,\,Final ECFinal就结束了以后应该要多打 c f cf cf比赛练习保持手感争取下赛季冲一下金牌。 感觉这个 d i v 3 div3 div3的难度还不错正常状态应该能做到差一题 A K AK AK思维含量还没有太高适合我这种fw选手。
A. Rook
题面 题意一个空的国际象棋棋盘给你车的初始位置问你挪动一步这个车可以到达哪些位置。 S o l u t i o n : Solution: Solution:按行按列输出即可注意初始的点不要输出。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 1e510;
const ll mod 998244353;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
int n,t;
char chr,ch;
void solve(){chrgetchar();while(chra||chrz)chrgetchar();chgetchar();while(ch0||ch9)chgetchar();nch-0;for(int i1;i8;i){if(in)continue;printf(%c%d\n,chr,i);}for(int i1;i8;i){if(ai-1chr)continue;printf(%c%d\n,ai-1,n);}
}
int main(){read(t);while(t--)solve();return 0;
}B. YetnotherrokenKeoard
题面 题意一个奇怪的键盘按小写 b b b是删掉目前已经打的最后一个小写字母按大写 B B B是删掉目前已经打的最后一个大写字母如果没有则不删打 b / B b/B b/B不会打出来字符只会删掉字符给出键盘按下的顺序求最后打出的内容。 S o l u t i o n Solution Solution个人做法是从头开始记录目前最后一个小写、大写字母的位置然后遇到 b / B b/B b/B就删除那个位置的字符并更新目前最后一个小写、大写字母的位置写的比较麻烦。赛后看题解发现倒序维护 b / B b/B b/B的数量遇到大小写直接删除是最快的最方便的。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 1e610;
const ll mod 998244353;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
int n,t,len,l[N],L[N],p,P,lst[N],LST[N];
char s[N];
void solve(){scanf(%s,s);lenstrlen(s);pP0;lst[0]LST[0]-1;for(int i0;ilen;i){if(s[i]As[i]Z){if(s[i]B){if(P){s[L[P]]0;P--;}s[i]0;}else L[P]i;}else{if(s[i]b){if(p){s[l[p]]0;p--;}s[i]0;}else l[p]i;}}for(int i0;ilen;i){if(s[i]!0)putchar(s[i]);}puts();
}
int main(){read(t);while(t--)solve();return 0;
}C. Removal of Unattractive Pairs
题面 题意对于一个字符串可以进行的操作是删掉相邻两个不相同的字符问最后最少剩下几个字符。 S o l u t i o n Solution Solution之前做过类似结论的题对于出现最多的字符的出现次数 t t t如果 t ≤ ⌊ l e n 2 ⌋ t\le\lfloor\frac{len}{2}\rfloor t≤⌊2len⌋则不会剩下字符否则剩下字符数为 t − ( t − ⌊ l e n 2 ⌋ ) t-(t-\lfloor\frac{len}{2}\rfloor) t−(t−⌊2len⌋)。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e510;
const ll mod 998244353;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
int n,t;
int cnt[30];
char s[N];
void solve(){read(n);for(int i0;i26;i)cnt[i]0;for(int i1;in;i){s[i]getchar();while(s[i]a||s[i]z)s[i]getchar();cnt[s[i]-a];}int m0;for(int i0;i26;i){if(cnt[i]m)mcnt[i];}if(mn-m){if(n1)puts(1);else puts(0);}else printf(%d\n,m-nm);
}
int main(){read(t);while(t--)solve();return 0;
}D. Jumping Through Segments
题面 题意一个坐标轴上有 n n n条线段从原点 0 0 0开始移动 n n n次每次移动到第 i i i条线段上这些移动的最大距离 ≤ k \le k ≤k求 k k k的最小值。 S o l u t i o n Solution Solution二分 k k k判断 k k k是否可行我们通过一个贪心的思想来模拟。 首先对于当前位置 n o w now now判断其在目标线段的左侧还是右侧如果在左侧则要向左移动在右侧则要向右移动这两种情况是等价的我们以向右移动为例子。 如果向右移动到目标线段的左侧发现还可以继续移动这时我们就维护一个 l , r l,r l,r代表目前可以向左、右走的多余距离。例如上述情况我们的 l 0 , r l0,r l0,r剩余的移动距离。 每当我们移动距离 k k k发现仍然到不了目标线段时此时就要用到这个多余距离来判断能否通过上一步剩余的距离来使我们移动到目标线段。 对于当前位置正好在目标线段的情况向左向右的多余距离分别为该位置到左右端点的距离。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e510;
const ll mod 998244353;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
int n,t,l[N],r[N];
bool check(int x){int now0,suml0,sumr0,movl0,movr0;for(int i1;in;i){int cnt0;if(nowl[i]){cntl[i]-now;movrmin(r[i]-l[i],x-cnt);if(movr0){if(sumrmovr0)return false;}sumrmovr,sumrmin(sumr,r[i]-l[i]),suml0;nowl[i];}else if(nowr[i]){cntnow-r[i];movlmin(r[i]-l[i],x-cnt);if(movl0){if(sumlmovl0)return false;}sumlmovl,sumlmin(suml,r[i]-l[i]),sumr0;nowr[i];}else{sumlmin(xsuml,now-l[i]),sumrmin(xsumr,r[i]-now);}}return true;
}
void solve(){read(n);for(int i1;in;i)read(l[i]),read(r[i]);int le0,ri1e9,mid0;while(leri){int midleri1;if(check(mid))rimid;else lemid1;}printf(%d\n,ri);
}
int main(){read(t);while(t--)solve();return 0;
}E. Good Triples
题面 题意给你 n n n 问你有多少组 ( a , b , c ) (a,b,c) (a,b,c)使得 a b c n abcn abcn 并且 a , b , c a,b,c a,b,c的每个位数的和等于 n n n的位数的和。 S o l u t i o n : Solution: Solution:很显然每一位不能有进位以为数字和相等所以对每一位都是独立考虑各个位之间的方案数乘起来即是答案。 对于每一位的答案赛时是通过观察样例前几个得到的答案其实推也很好推不想推一个一个写也写出来了答案就是 0 1 ⋯ i 01\dotsi 01⋯i对于这一位为 i i i。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e510;
const ll mod 998244353;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
int n,t,a[]{1,3,6,10,15,21,28,36,45,55};
void solve(){read(n);ll s1;while(n){s*1ll*a[n%10];n/10;}printf(%lld\n,s);
}
int main(){read(t);while(t--)solve();return 0;
}F. Shift and Reverse
题面 题意对于一个序列你可以做两种操作第一种是把最后一个放到最前面第二种是把整个序列倒序问最少用几次操作可以把数列变为从小到大的。不能变则输出 − 1 -1 −1。 S o l u t i o n Solution Solution如果把这个序列当成循环序列不难发现第一种操作没有改变序列第二种操作只是改变了顺序和倒序因此如果序列最开始不是顺序或逆序则不能变为有序数列。 对于可以改变的序列我们要找到序列的起始点再分别判断先改变位置再倒序和先倒序再改变位置哪个更优输出操作次数最少的那个即可。 赛时有点困想出来的时候还有 5 5 5分钟再加上想出来的方法比较麻烦所以就没做这个题实际上直接倍长数组就比较方便。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e510;
const ll mod 998244353;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
int n,t,a[N1];
void solve(){read(n);for(int i1;in;i)read(a[i]),a[in]a[i];int b1,s1,now0,ansn1;for(int i2;in*2;i){if(a[i]a[i-1])b,s1;else if(a[i]a[i-1])s,b1;else s,b;if(sn||bn){nowi-n1;if(sn)ansmin(ans,min(1n-now1,now));if(bn)ansmin(ans,min(n-now1,2now-1));}}if(ans!n*2)printf(%d\n,ans);else puts(-1);
}
int main(){read(t);while(t--)solve();return 0;
}G. Lights
题面 题意你有 n n n个灯有开有闭想把这些灯全关了但是灯有个性质是每按一次灯 i i i开关灯 a i a_i ai的开关也会被按一次问你最少多少次能把这些灯全关了不能全关输出 − 1 -1 −1。 S o l u t i o n Solution Solution把 i i i和 a i a_i ai连出一条边就会获得一个 n n n个点 n n n条边的一张图这个图会由若干棵基环树组成对于每棵树我们先处理他的叶子节点随后删掉叶子节点最后剩下一个环在这个环上我们每次操作都是动偶数个灯因此如果环上有奇数个灯开着那么就无法全部关闭输出 − 1 -1 −1。对于环上有两种情况一种是从起点开始关一种是从起点的下一个点开始关这个起点可以随意设置因为环上是等价的选出这两种情况关闭数量最少的一个进行关灯即可。
#includebits/stdc.h
using namespace std;
inline void read(int x){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){s(s3)(s1)(ch15);chgetchar();}xs*w;
}
const int N 2e5 100;
int T,n,cd[N],e[N],a[N],cc[N];
void solve(){read(n);for(int i1;in;i){char chrgetchar();while(chr!0chr!1)chrgetchar();cc[i]cd[i]chr15;}vectorsetint s(n1);queueint p;int ans0;for(int i1,x;in;i){read(x);e[i]x;s[x].insert(i);}for(int i1;in;i)if(s[i].size()0)p.push(i);while(!p.empty()){int ip.front();p.pop();if(cd[i]1){s[e[i]].erase(i);cd[i]^1,cd[e[i]]^1;a[ans]i;if(s[e[i]].size()0)p.push(e[i]);}else{s[e[i]].erase(i);if(s[e[i]].size()0)p.push(e[i]);}}for(int now1;nown;now){if(cd[now]){vectorint c;int sum1;if(cd[now])c.push_back(1);for(int ie[now];i!now;ie[i]){sum;if(cd[i])c.push_back(sum);}if(c.size()1){puts(-1);return ;}int s10,s2c[0]sum-c[c.size()-1];for(int i1;ic.size();i){if(i1)s1c[i]-c[i-1];else s2c[i]-c[i-1];}int stnow;if(s2s1)ste[now];for(int ist;;ie[i]){if(cd[i]){a[ans]i;cd[i]^1,cd[e[i]]^1;}if(e[i]st)break;}}}printf(%d\n,ans);for(int i1;ians;i)printf(%d ,a[i]);puts();return ;
}
int main(){read(T);while(T--)solve();return 0;
}
