机票
战绩and总结
发现D大模拟有bug的时候，发现E可以做，调到最后三十秒交wa了心态都蹦了，赛后十分钟过了E 😦 太难见到比较简单的1700分的题了
A. Integer Sequence Dividing
题意：给你一个数n，求把1~n的整数分为两组，使得每组的和的差的绝对值最小。
思路：比赛的时候枚举推出了正解，但是我写的比较复杂也不知道证明，这里贴一个：每当n+4时，必然可以将多出来的4个值分为n+1和n+4 与 n+2和n+3，所以差不变，所以往n%4去想
n%4=3时，1 2 3 的差值为0，所以也是0
n%4=2时，1 2 显然差1
n%4=1时，同上，差为1
n%4=0时，差值为0
#include<iostream> using namespace std; int main() { int a; cin>>a; if(a%4==0){cout<<'0';return 0;} if(a%4==2){cout<<'1';return 0;} if(a%4==3){cout<<'0';return 0;} if(a%4==1){cout<<'1';return 0;} return 0; }
B. Array K-Coloring
题意：长为n的序列a和k种颜色，要求①每个元素都要被染色，②每种颜色都要被使用，③每种颜色不会用于相同的元素。
思路： 我暴力模拟的就不贴了，看到了一个比较牛的思路贴一下：
解决问题有两个：
1.用上所有颜色
2.每种相同数字的颜色不同
对于第一个，简单地，只需设置一个变量color，一直++，超过了颜色数就再次从1开始
对于第二个，为了让相同数字排在一起我们需要一次sort，之后就只要保证该种数字的数量小于颜色数就好了
对于输出，按照读入顺序再次sort即可
const int maxn=5005; int a[maxn]; int ans[maxn]; int main() { int n,i,j,k,max1=0,mm; cin>>n>>k; bool flag=0; map<int ,int >mo; for(i=0;i<n;i++){ cin>>a[i]; mo[a[i]]++; if(mo[a[i]]>max1) { max1=mo[a[i]]; mm=a[i]; } if(max1>k) { flag=1; } ans[i]=mo[a[i]]; } if(flag==0&&n>=k) { scYES; if(max1==k) { for(i=0;i<n;i++) { if(ans[i]==0) ans[i]=1; } } else { for(i=0;i<n;i++) { if(a[i]!=mm&&max1<k) ans[i]=++max1; } } for(i=0;i<n-1;i++) cout<<ans[i]<<" "; cout<<ans[i]<<endl; } else { scNO; } }
C. Doors Breaking and Repairing
题意：给你一个含有N个数的数组，每一个元素代表一个门的当前防御值。
每一次你可以对门进行攻击，降低x个点数的防御值；而你的对手（斯拉维克）可以对门进行修复，提升y个点数的防御值。
当一次你对门的攻击使这个门的防御值小于等于0的时候，这个门就坏掉了，就再也没法修复了。
问：当你和对手都采取最优的策略的时候，你最多可以砸坏几个门？
思路：
如果 x > y，所有门的总血量每回合都会减少，经过无限个回合，所有的门一定都会被打破。
否则就是 x≤y 的情况，发现那些血量 > x的门A永远打不破，因为A打一下，B就可以加固那扇门，血量 ≤x 的门，A打破一扇，B就加固一扇门，A只能打破一半（A先手，要上取整）
const int maxn=1e5+100; int a[maxn]; int main() { int x,y,n,i,j; cin>>n>>x>>y; for(i=0;i<n;i++) { cin>>a[i]; } if(x>y) { cout<<n<<endl; } else { double cnt=0; for(i=0;i<n;i++) { if(a[i]<=x) { cnt++; } } cout<<(int)(cnt/2+0.5)<<endl; } }
D. Balanced Ternary String
题意：给出一个长为n的只由’1’,‘2’,‘0’组成的字符串，要求改动最少的位置，使’1’,‘2’,'0’的个数相同（保证n能被3整除），并使改动后的字符串字典序最小。输出改动之后的字符串
思路：由于我这个贪心贪少了，所以贴贴大佬的思路，我是在三种情况的顺序上出现了问题。
#include <cstdio> int n, qui; char s[300005]; int cnt[105]; // 注意每次修改元素后要及时修改 cnt 数组 int main() { scanf("%d", &n); qui = n/3; scanf("%s", s+1); for(int i = 1; i <= n; ++i) ++cnt[(int)s[i]]; for(int i = 1; cnt['2'] > qui && i <= n; ++i) { if(s[i] == '2') { if(cnt['0'] < qui) s[i] = '0', ++cnt['0'], --cnt['2']; else if(cnt['1'] < qui) s[i] = '1', ++cnt['1'], --cnt['2']; } } for(int i = n; cnt['0'] > qui && i; --i) { if(s[i] == '0') { if(cnt['2'] < qui) s[i] = '2', ++cnt['2'], --cnt['0']; else if(cnt['1'] < qui) s[i] = '1', ++cnt['1'], --cnt['0']; } } for(int l = 1, r = n; cnt['1'] > qui && r; ++l, --r) { if(s[l] == '1' && cnt['0'] < qui) s[l] = '0', ++cnt['0'], --cnt['1']; if(s[r] == '1' && cnt['2'] < qui) s[r] = '2', ++cnt['2'], --cnt['1']; } puts(s+1); return 0; }
E. Monotonic Renumeration
题意：定义一个数组a的b数组为满足下列条件的数组
①b[1]=0
②如果ai=aj，那么bi=bj
③b[i]=b[i-1]+1 或者 b[i]=b[i−1]
给出a，求合法的b的数量 %998244353
思路：首先看题目给出的条件，模拟去构造一下B，因为第三点可知这个数列一定是个非递减序列，并且如果ai=aj的话，那么这个区间上所有的b的值都唯一那么计算数量的时候就可以从这里入手，假设长度为n的a数组里所有的数都不同，那么对应的b数组的个数应该就是2^n次方，因为每个b[i+1]的取值都可以是b[i]或者b[i]+1，所以只要记算一下b区间里不重复的个数就行
那么怎么计算呢？可以把它转化为区间合并问题，看最后b数组能分成cnt个不相交的区间，最后结果就是2^cnt-1%998244353了
#define int long long const int maxn=2e5+1000; int a[maxn]; struct node { int l,r; }mo[maxn],ly[maxn]; bool cmp1(node a,node b) { return a.l<b.l; } signed main() { int n,i,j; cin>>n; map<int ,int >m2; map<int ,pair<int ,int >>m1; for(i=0;i<n;i++){ cin>>a[i]; m2[a[i]]++; if(m2[a[i]]==1) m1[a[i]].first=i+1,m1[a[i]].second=i+1; else m1[a[i]].second=i+1; } int cnt=0; for(auto x:m1) { mo[cnt].l=m1[x.first].first; mo[cnt++].r=m1[x.first].second; } sort(mo,mo+cnt,cmp1); int cnt1=0,z1=0; for(i=0;i<cnt;i++) { if(mo[i].l>ly[max(cnt1-1,0ll)].r) { ly[cnt1].l=mo[i].l; ly[cnt1].r=mo[i].r; cnt1++; } else { ly[max(cnt1-1,0ll)].r=max(ly[max(cnt1-1,0ll)].r,mo[i].r); } } if(n==1) { cout<<1<<endl; } else if(cnt1==0) cout<<2<<endl; else cout<<quickpowmod(2,cnt1-1,998244353)<<endl; return 0; }
