A. Contest Proposal
Problem - A - Codeforces
题目大意：
给定数组ai和bi，这俩数组都是非递减的。每次操作可以在ai的前面放上任意数字w，并删去a数组末尾的元素，求最少多少次操作让ai<=bi。
思路：
模拟几个样例之后发现就是求最少把a数组右移多少位。
其实我想了下贪心并不好做，看了下数据范围直接二分就好了（直接暴力好像也行）。二分有思路之后其实就很好做了，枚举要做x次操作，check函数之后比较a数组中从i-n-x，b数组从x+1-n，比较即可。
#include<bits/stdc++.h>
using ll=long long;
const int N=1e3+10;
int a[N],b[N];
int n;
bool check(int x)//要删去几个
{for(int i=1,j=x+1;i<=n-x,j<=n;i++,j++){if(a[i]>b[j]) return false;}return true;
}
void solve()
{std::cin>>n;for(int i=1;i<=n;i++) std::cin>>a[i];for(int i=1;i<=n;i++) std::cin>>b[i];int l=0,r=n,res=-1;while(l<=r){int mid=l+r>>1;if(check(mid)){res=mid;r=mid-1;}else{l=mid+1;}}std::cout<<res<<'\n';
}
signed main()
{std::ios::sync_with_stdio(0);std::cin.tie(nullptr);int t=1;std::cin>>t;while(t--){solve();}return 0;
}B. Coin Games
Problem - B - Codeforces
题目大意：
给n个硬币，每次能选择一个正面朝上的硬币把他拿走，并且翻转相邻的两个硬币（这题硬币是成环放置的）。如果没有正面朝上的硬币可拿，就输了。求解先手能否必胜。
思路：
感觉这题比cd难啊，可能我是真的不太会写博弈论（加训.jpg)。
这题必输态是U的个数为0，如果我们手捏几种情况：
UUU,DUD,UUD,DUU->DD,UU,DU,UD
3个u会变成0个u，2个u变成1个u，1个u变成2个u
每次取走u都会让u的个数-3/-1/+1，因此每次都会改变u个数的奇偶性。
如果遇到是UU，必败。如果遇到是U，必胜。因此猜结论，u为偶数个必败，奇数必胜。
U的个数为0显然是一个必败局面。
对任意一个局面，如果有U的个数为奇数，alice操作完之后U的个数一定是偶数，如果bob能操作，操作完之后一定是奇数，最小的奇数就是1，所以alice一定不会输。所以alice必赢。因此U的个数为奇数是一个必胜局面。
对任意一个局面，如果有U的个数为偶数，alice操作完之后U的个数一定是奇数，此时对于bob这是一个必胜局面，alice必输。因此U的偶数是一个必败局面。
#include<bits/stdc++.h>
using ll=long long;
const int N=1e3+10;
int a[N],b[N];
int n;
void solve()
{std::cin>>n;std::string s;std::cin>>s;int len=s.size();//遇到正反/反反 win//遇到 正正 输int cnt=0;for(int i=0;i<len;i++){if(s[i]=='U') cnt++;}if(cnt%2) std::cout<<"YES"<<'\n';else std::cout<<"NO"<<'\n';
}
signed main()
{std::ios::sync_with_stdio(0);std::cin.tie(nullptr);int t=1;std::cin>>t;while(t--){solve();}return 0;
}C. Permutation Counting
Problem - C - Codeforces
题目大意：
给一些牌编号从1到n，给你k个硬币，可以买k张任意的牌。
输入一个数组，ai代码编号为i的牌有几张。
输出最后1-n的排列的个数。思路：
模拟一遍样例之后会发现，123123123123，这种4个123的情况会有4+3+3种可能，那么对于任意1-n的排列如果有m个，答案就是m+（m-1）*（n-1）。还有特别的情况，比如3123123，这种情况会多一种，因此我们再循环一遍多余的数字有几种，加上就是答案。
然后就是我们需要k次操作之后让1-n的完整排列数最多，也就是让数组中最小的数字最大。我一开始脑瘫写了个堆模拟，爽超时。（k是1e12，while(k)必超时的啊，又被自己蠢到了）。
最小的数最大，这不是妥妥的二分吗，只要有二分的思路基本都很好写和debug，所以我果断换了二分。然后就是注意二分的边界大小。
#include<bits/stdc++.h>
using ll=long long;
#define int ll
const int N=2e5+10;
int a[N],b[N];
int n,k;
bool check(int x)
{ll sum=0;for(int i=1;i<=n;i++){if(a[i]<x){sum+=x-a[i];}if(sum>k) return false;}return true;
}
void solve()
{std::cin>>n>>k;//std::priority_queue<int,std::vector<int>,std::greater<int>> q;//小根堆for(int i=1;i<=n;i++){std::cin>>a[i];b[i]=a[i];//q.push(a[i]);}int t=0;int l=0,r=1e15,res=-1;while(l<=r){int mid=l+r>>1;if(check(mid)){l=mid+1;res=mid;}else r=mid-1;}t=res;//最小是这么多//std::cout<<t<<"xxxxxxxxx"<<'\n';ll sum=0;for(int i=1;i<=n;i++){if(a[i]<t){sum+=t-a[i];//已经用上的a[i]=t;}}sum=k-sum;for(int i=1;i<=n&&sum>0;i++){if(a[i]==t){sum--;a[i]++;}}ll ans=t+(t-1)*(n-1);for(int i=1;i<=n;i++){if(a[i]>t) ans++;}std::cout<<ans<<'\n';
}
signed main()
{std::ios::sync_with_stdio(0);std::cin.tie(nullptr);int t=1;std::cin>>t;while(t--){solve();}return 0;
}D1. Reverse Card (Easy Version)
Problem - D1 - Codeforces
题目大意：
求满足条件的有序对（a，b）的个数。
思路：
multiple不是乘积的意思，我一开始误解题意浪费了好多时间，
然后会发现（a+b）/b=gcd（a，b）*k，那么a一定是b的倍数。我们枚举即可。
#include<bits/stdc++.h>
using ll=long long;
//#define int ll
const int N=2e6+10;
int a[N],b[N];
int n,m;
void solve()
{std::cin>>n>>m;ll cnt=0;for(int i=1;i<=m;i++){for(int j=1;(ll)j*i<=n;j++){ll a=j*i,b=i;if((a/b+1)%(std::__gcd(a,b))!=0) continue;//std::cout<<a<<" "<<b<<'\n';cnt++;}}std::cout<<cnt<<'\n';
}
signed main()
{std::ios::sync_with_stdio(0);std::cin.tie(nullptr);int t=1;std::cin>>t;while(t--){solve();}return 0;
}
