基础训练（4）
1.Problem - 1651C - Codeforces
可以发现边界必须连边，然后就考虑对边界连边，发现最多连四条边，如果都是边界连接边界就是两条边。所以就直接考虑总共连接2，3，4条边。
const int N=2e5+100;
int n;
int a[N],b[N];
void slove(){
cin>>n;
fel(i,1,n) cin>>a[i];
fel(i,1,n) cin>>b[i];
int t1,t2,t3,t4;
t1=t2=t3=t4=1e18;
fel(i,1,n){
t1=min( t1, abs(a[1]-b[i]) );
t2=min( t2, abs(a[n]-b[i]) );
t3=min( t3, abs(b[1]-a[i]) );
t4=min( t4, abs(b[n]-a[i]) );
}
int ans=1e18;
ans=min({
abs(a[1]-b[1])+abs(a[n]-b[n]),
abs(a[1]-b[n])+abs(a[n]-b[1]),
abs(a[1]-b[1])+t2+t4,
abs(a[1]-b[n])+t2+t3,
abs(a[n]-b[1])+t1+t4,
abs(a[n]-b[n])+t1+t3,
t1+t2+t3+t4
});
cout<<ans<<endl;
}
2.Problem - 1594C - Codeforces
wa了两发，后面发现只有在n/2+1的区间内可以找到一个满足条件的字母就只需要一次了。
void slove(){
cin>>n>>op;
cin>>s;
s=" "+s;
int pos=0,cnt=0;
for(int i=n/2+1;i<=n;i++){
if(s[i]==op){
pos=i;
break;
}
}
for(int i=1;i<n;i++){
if(s[i]!=op){
cnt++;
break;
}
}
if(cnt==0&&s[n]==op){
cout<<0<<endl;
}
else if(pos){
cout<<1<<endl;
cout<<pos<<endl;
}
else{
if(cnt==1&&s[n]==op){
cout<<1<<endl;
cout<<n<<endl;
}
else if(cnt==1&&s[n]!=op){
cout<<2<<endl;
cout<<n-1<<" "<<n<<endl;
}
}
}
3.Problem - D - Codeforces
2200分的题其实思维难度不算高。首先新矩阵必须对应是前面矩阵的倍数，原矩阵1-16的值域。我可以考虑直接求他们的lcm。然后又因为相邻格子之间差位k的四次方。发现需要加四次方的格子一定是间隔的。所以直接考虑这些格子直接加上原矩阵对应点的四次方即可。
void slove(){
cin>>n>>m;
int lcm=1;
for(int i=2;i<=16;i++){
lcm=lcm*i/__gcd(lcm,i);
}
fel(i,1,n){
fel(j,1,m){
cin>>mp[i][j];
}
}
fel(i,1,n){
fel(j,1,m){
if((i+j)&1) cout<<lcm<<" ";
else cout<<lcm+pow(mp[i][j],4)<<" ";
}
cout<<endl;
}
}
4.Problem - C - Codeforces
就是求a / b =a % b的对数。发现a / b = a % b = i你是很容易求出来多少对的。1 <= i < y
此时只需要判断确定b就可以确定a了，所以就直接确定符合条件的b有多少个。b的最小值和最大值都很好确定。
void slove(){
cin>>a>>b;
int ans=0;
for(int i=1;i<b;i++){
if(i*(i+2)>a) break;
int t1=i+1;
int t2=min(a/i-1,b);
ans+=t2-t1+1;
}
cout<<ans<<endl;
}
5.Problem - C - Codeforces
很明显每个人可以进行的比赛场出是可以确定的都是n-1场，要使平局尽量少。那就显而易见了。n-1是偶数就一半win一般lose。奇数就多一把平局即可。
void slove(){
cin>>n;
fel(i,1,n) sum[i]=vis[i]=0;
if(n%2){
int cnt=(n-1)/2;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(sum[i]<cnt){
cout<<1<<" ";
sum[i]++;
}
else{
cout<<-1<<" ";
sum[j]++;
}
}
}
cout<<endl;
}
else{
int cnt=(n-1)/2;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(sum[i]<cnt){
cout<<1<<" ";
sum[i]++;
}
else if(sum[i]==cnt&&vis[i]==0){
cout<<0<<" ";
vis[i]=1,vis[j]=1;
sum[i]++;
}
else{
cout<<-1<<" ";
sum[j]++;
}
}
}
cout<<endl;
}
}
6.Problem - C - Codeforces
这个题写过两遍了，思想还是很明确的。
很明显后面是无法踩到前面的，所以得先把前面的点先变成1.然后考虑他的贡献。这个贡献很好求，用差分就好。然后考虑如果前面对这个点产生的贡献大于a[i]-1那么多余的贡献就会贡献给下面那一个点。
void slove(){
cin>>n;
fel(i,1,n){
cin>>a[i];
b[i]=0;
}
int ans=0;
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
int t=b[i];
if(b[i]<a[i]-1){
ans+=a[i]-1-b[i];
t+=a[i]-1-b[i];
}
b[i+1]+=t-a[i]+1;
b[i+2]-=t-a[i]+1;
if(i+2<=n){
b[i+2]++;
b[min(n+1,a[i]+i+1)]--;
}
}
cout<<ans<<endl;
}
7.Problem - D - Codeforces
可以很简单的发现u可以到u+v需要满足什么条件呢？
需要在u是的0位置必须是0，u是一的位置随便你。这一在&之后可以明显发现只肯定是等于v的，然后再两个相加你发现肯定是会使x的1向高位移动.并且这种移动是可能减少1的。所以只要保证x的后缀1的个数大于y即可。这样通过移动肯定是可以变成你的。
void slove(){
int x,y;
cin>>x>>y;
if(x>y){
cout<<"NO"<<endl;
return;
}
else{
int cnt1=0,cnt2=0;
for(int i=0;i<30;i++){
if((x>>i)&1) cnt1++;
if((y>>i)&1) cnt2++;
if(cnt2>cnt1){
cout<<"NO"<<endl;
return;
}
}
}
cout<<"YES"<<endl;
}
8.Problem - B - Codeforces
很容易想到这一行如果对另外一行产生影响的可能只有>n-2时。然后考虑对另外两行的影响是什么。如果是等于n的很明显是会对两行都产生+1的影响，如果是n -1 则是对任意一行产生影响。然后判断是否有可能产生的贡献比你原来的还多就可以了。
void slove(){
int n,u,r,d,l;
cin>>n>>u>>r>>d>>l;
int cnt1,cnt2,cnt;
cnt1=cnt2=cnt=0;
if(u==n) cnt1++,cnt2++;
if(u==n-1) cnt++;
if(d==n) cnt1++,cnt2++;
if(d==n-1) cnt++;
if(cnt1>l||cnt2>r||cnt1+cnt2+cnt>l+r){
cout<<"NO"<<endl;
return;
}
cnt1=cnt2=cnt=0;
if(l==n) cnt1++,cnt2++;
if(l==n-1) cnt++;
if(r==n) cnt1++,cnt2++;
if(r==n-1) cnt++;
if(cnt1>u||cnt2>d||cnt1+cnt2+cnt>d+u){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
}
9.Problem - C - Codeforces
这个题第二遍写了还是没写出来。首先分正负数考虑是很明显的。
然后枚举特殊点，我把后面所有点都移动到以这个点为末尾向更近端端延伸然后再加上后面已经踩在特殊点上的点。找正负数的最大值即可。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fel(i,x,y) for(int i=x;i<=y;i++)
#define fhl(i,x,y) for(int i=x;i>=y;i--)
#define inf 0x3fffffff
#define ll long long
#define pb push_back
#define endl "\n"
#define int long long
//大概意思就是分正负数讨论，情况是一样的
//我考考虑枚举移动的箱子视为一连串，将b数组视为结尾，然后看有多少找最大值
const int N=2e5+100;
int n,m;
int a[N],b[N],box[N],q[N];
map<int,int>mp;
int add(int lena,int lenb){
int count=0,res=0,ans=0;
mp.clear();
fel(i,1,lena) mp[a[i]]=1;
fel(i,1,lenb) if(mp[b[i]]) count++;
res=count;
ans=count;
for(int i=1;i<=lenb;i++){//枚举火车头
if(mp[b[i]]){
res--;//表示后面还有多少点踩在上面
continue;
}//当你碰到一个新的火车头你前面求得得那一段的最大值如果在将这个视为火车头，最大值最多也就是ans+1(上一回合不变，这个点继续保持原位置也是ans+1),
//所以上一回合求出来的最大值如果把火车以此点作为头话，最大值肯定是会变小的或者不变的
int p=upper_bound(a+1,a+1+lena,b[i])-a-1;//把b[i]作为火车头的火车有多长//upper求得是第一个大得位置，所以还要前去1
int qq=lower_bound(b+1,b+1+lenb,b[i]-p+1)-b;//刚好有箱子的第一个位置
ans=max(ans,res+i-qq+1);//res是后面匹配的位置，i-q+1是q到i这一段的长度
}
return ans;
}
void slove(){
cin>>n>>m;
fel(i,1,n) cin>>box[i];
fel(i,1,m) cin>>q[i];
int lena=0,lenb=0;
fel(i,1,n) if(box[i]>=0) a[++lena]=box[i];
fel(i,1,m) if(q[i]>=0) b[++lenb]=q[i];
int ans=add(lena,lenb);
lena=0,lenb=0;
fhl(i,n,1) if(box[i]<0) a[++lena]=-box[i];
fhl(i,m,1) if(q[i]<0) b[++lenb]=-q[i];
ans+=add(lena,lenb);
cout<<ans<<endl;
}
10.Problem - 1725G - Codeforces
直接考虑a=b+1，a=b+2即可。后面的情况这都包含了。
void slove(){
int n;
cin>>n;
if(n==1) cout<<3<<endl;
else if(n==2) cout<<5<<endl;
else if(n==3) cout<<7<<endl;
else{
int t=n%3;
n-=3;
int ans=8+(n-1)/3*4;
if(t==2) ans++;
if(t==0) ans+=3;
cout<<ans<<endl;
}
}
标签：cnt,cout,int,cin,++,基础训练,ans
From： https://www.cnblogs.com/silky----player/p/16774229.html