?好久没打cf了，这两天一直配linux，写django，脑子都麻了

过几天补补题康复一下

目录

A. Make it Beautiful

B. Matrix of Differences

C. Yet Another Tournament

D. Different Arrays

E. Game of the Year

---

?

A. Make it Beautiful

首先数组是排好序的

这样只要第一个等于最后一个就说明所有元素都相等，这肯定是NO

否则我们只需要将数组第2-n这一段反转，保留第一个数

这样即便是丑陋的也会变成美好的

输出即可

代码如下

#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'\n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1e6+10; signed main() { int T; cin>>T; while(T--){ int n; cin>>n; vector<int> a(n); for (int i=0;i<n;i++){ cin>>a[i]; } if(a[0]==a[n-1]) { cout<<"NO\n"; } else{ cout<<"YES\n"; reverse(a.begin()+1,a.end()); for (int i=0; i<n;i++){ cout<<a[i]<<" \n"[i==n-1]; } } } } B. Matrix of Differences

看样例可以得到一个规律

就是给一个n，得到的结果必然是1,2,3.....n*n-1这n*n-1个数

我们就可以蛇形排列了

#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'\n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1e6+10; int a[100][100]; signed main() { int T; cin>>T; while(T--){ int n; cin>>n; int nw=0,L=1,R=n*n,flag=0; fer(i,1,n) { if(i&1) { for(int j=1;j<=n;j++) { if(flag) a[i][j]=L++; else a[i][j]=R--; flag^=1; } } else { for(int j=n;j>=1;j--) { if(flag) a[i][j]=L++; else a[i][j]=R--; flag^=1; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout << a[i][j] << " "; cout << "\n"; } } } C. Yet Another Tournament

题目意思就是最开始有n个人，他们最开始有1 2 3.....n场胜利

每次花费a[i]可以将第i个人的胜利数量-1，你的胜利数量+1

求最好的结果你可以排第几

假设你现在想排第一，怎么才能排第一呢？

有两种情况

一是你从1-n这n个人中战胜其中的n-1个人，并且必须包含第n个人，这样你就可以和第n个人并列第一了

二是你从1-n这n个人中战胜其中的n个人，这样可以直接排第一（虽然看起来像是废话）

我们在举一个例子

假设有n个人，你想排第3

一是你从1-n这n个人中战胜其中的n-3个人，并且必须包含第n-2个人，这样你就可以和第n-2个人并列第3了

二是你从1-n这n个人中战胜其中的n-2个人，这样可以直接排第3（这里可能优化的点在于，第n-2个人可能权值很高，你可以通过战胜后面两个人（n-1，n）来优化你的结果）

这就可以二分了

代码如下

#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'\n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1e6+10; pll w[N]; int ww[N]; int n,m; bool check(int k){ if(k==n+1) return 1; if(k==n){ if(m>=w[1].first){ return 1; } else{ return 0; } } int res=0; res+=ww[n-k+1]; int use=1; fer(i,1,n){ if(use>=n-k) break; if(w[i].second==n-k+1){ continue; } else{ res+=w[i].first; use++; } if(use>=n-k) break; } int res2=0; fer(i,1,n-k+1){ res2+=w[i].first; } if(res<=m || res2<=m) return 1; return 0; } signed main() { int T; cin>>T; while(T--){ cin>>n>>m; int tmp; fer(i,1,n){ cin>>tmp; ww[i]=tmp; w[i].first=tmp; w[i].second=i; } sort(w+1,w+1+n); int l=1,r=n+1; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout<<l<<'\n'; } } D. Different Arrays

题意就是每次操作可以将以一个数为中心，一个邻居加上他一个邻居减去他

问操作n-2次之后，可以得到多少不同的数组

很明显的dp题

dp[i][j]表示操作第i个数，后缀是j的可能数量

这样转移方程就是

dp[i+1][a[i+1]+j]+=dp[i][j]

dp[i+1][a[i+1]-j]+=dp[i][j]

而且需要特判0，因为当被操作的数是0时，那个邻居加或减是等效的，注意不要加两次

因为数组下标不能有负数，所以我们加一个哈希值，将其映射到远处的一个点，表示减

代码如下

#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'\n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1e6+10; const int hx=90000; int dp[305][180005]; int a[505]; const int mod=998244353; signed main() { int n; cin >> n; fer(i,1,n) cin>>a[i]; dp[2][a[2]+hx]=1; for(int i=2;i<n;i++) { for(int j=0;j<=hx+hx;j++) { if(dp[i][j]) { if(j!=hx) { dp[i+1][a[i+1]+j]+=dp[i][j]; dp[i+1][a[i+1]-j+hx*2]+=dp[i][j]; } else dp[i+1][a[i+1]+j]+=dp[i][j]; } } for(int j=0;j<=hx+hx;j++) dp[i+1][j]%=mod; } int ans=0; for(int i=0;i<=hx+hx;i++) ans+=dp[n][i]; cout<<ans%mod; } E. Game of the Year

题意就是，给定n个boss，A打第i个boss要打掉a[i]的血，B打第i个boss要打掉b[i]的血

攻击可以叠加

如果A杀死了第i个boss（最后一击），那么打第i+1个boss也是A先出手

问一次攻击取什么值时，A可以抢到所有boss的最后一击

分析一下可以得知，对于任意一个答案，A打所有boss都是先出手那个（因为如果A后出手就说明前一个boss是B最后一击，这个数就不是答案了）

先出手就意味着，如果A[i]<B[i]那么无论K取何值时，A都是最后一击，也就是这种情况对答案没影响

反之A[i]>B[i],当K取B[i]到A[i]这一段，A就抢不到了，这种K是不行的

所以我们可以利用差分，维护B[i]到A[i]这一段，只要差分不为0，就不可以，反之可以

光这样还不行，比如A[i]等于5，B[i]等于3，我们只维护了3-5这一段的答案是不行的

但对于2和1，也是不行的，得想个办法

由于是回合制游戏，我们的K是可以玩倍增的，什么意思呢

攻击力为2和攻击力为4是等价的，同样也和6，8，10等价

这样我们就可以nlog筛所有答案了

代码如下

#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'\n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1e6+10; const int mod=998244353; int a[N],b[N],d[N]; signed main() { int T; cin>>T; while(T--){ int n; cin>>n; fer(i,0,n-1){ cin>>a[i]; d[i]=0; } d[n]=0; d[n+1]=0; fer(i,0,n-1){ cin>>b[i]; } fer(i,0,n-1){ if(a[i]>b[i]){ d[b[i]]++; d[a[i]]--; } } fer(i,1,n){ d[i]+=d[i-1]; } vector<int> ans; fer(k,1,n){ int ok=1; for(int i=k;i<=n;i+=k){ if(d[i]){ ok=0; break; } } if(ok) ans.push_back(k); } cout<<ans.size()<<"\n"; for(auto x:ans) { cout<<x<<" \n"[x == ans.back()]; } } }

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。