1355C - Count Triangles，2021CCPC桂林 C，D

65 阅读 0 评论 43 点赞

我是靠谱客的博主直率康乃馨，最近开发中收集的这篇文章主要介绍1355C - Count Triangles，2021CCPC桂林 C，D，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

14天阅读挑战赛

1355C - Count Triangles

枚举i=x+y的值，i一定是要>=c+1的，那么z的取值就是min(d+1,i)-c,再去看x和y的值，

x属于[a,b],y属于[b,c],a+b<=i<=b+c--->i-b>=a,i-c<=b,那么对于每一个y，x的取值就是max(i-c,a),min(i-b,b),那么x可取的数就是min(i-b,b)-max(i-c,a)+1,然后将x和z的个数相乘就是这个i对答案的贡献

C. Count Triangles(组合数学)_Harris-H的博客-CSDN博客

#include <bits/stdc++.h>
using namespace std;
#define endl 'n'
#define int long long
const int N = 2e5+5;
//const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int a,b,c,d;
signed main()
{
//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
cin>>a>>b>>c>>d;
int ans=0;
for(int i=max(a+b,c+1);i<=b+c;i++)
{
ans+=(min(d+1,i)-c)*(min(i-b,b)-max(i-c,a)+1);
}
cout<<ans<<endl;
return 0;
}
//

G - Occupy the Cities 二分

二分答案，check函数就是看看第i个零距离两侧的1是否小于等于x，不然就让右边的1向左感染，然后标记右边的1，表示这个右边的1如果作为左边的1的话已经被用了，不可以再向右感染了；否则可以向右感染；

#include <bits/stdc++.h>
using namespace std;
#define endl 'n'
#define int long long
const int N = 2e6+5;
//const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int n,t,pre[N],suf[N],pos[N],vis[N];
char s[N];
bool check(int x)
{
for(int i=1;i<=n;i++) pos[i]=i,vis[i]=0;
pos[0]=-inf;pos[n+1]=inf;
vis[0]=vis[n+1]=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='1') continue;
int l=pre[i],r=suf[i];
if(pos[l]==l&&!vis[l]) pos[l]=pos[l]+1;
int minn=min(i-pos[l]+1,pos[r]-i+1);
//cout<<minn<<" "<<i-pos[l]+1<<" "<<pos[r]-i+1<<" "<<x<<endl;
if(minn<=x) continue;
int tmp=pos[r]-1;vis[r]=1;
minn=min(i-pos[l]+1,tmp-i+1);
if(minn>x) return 0;
}
return 1;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
cin>>t;
while(t--)
{
cin>>n;
cin>>(s+1);
for(int i=1;i<=n;i++) pre[i]=suf[i]=pos[i]=0;
int last=0;
for(int i=1;i<=n;i++)
{
pre[i]=last;
if(s[i]=='1') last=i;
}
last=n+1;
for(int i=n;i>=1;i--)
{
suf[i]=last;
if(s[i]=='1') last=i;
}
pos[0]=-inf;pos[n+1]=inf;
int l=0,r=n,ans=n;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
}
return 0;
}
//
/*
11
000100001000
*/

1474C - Array Destruction multiset

每次都要选数组里的最大值，因为不选的话以后就没机会选了，然后再找一个上一个最大值与该最大值的差就可以，因为第一个最大值所对应的差值是不确定的，那就去枚举，除最大值外所有的数，然后看看是否符合条件

C. Array Destruction(思维+树形结构+枚举)_小菜鸡加油的博客-CSDN博客

#include <bits/stdc++.h>
using namespace std;
#define endl 'n'
#define int long long
const int N = 2e6+5;
//const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int t,n,a[2005],m,flag;
multiset<int>s;
vector<pair<int,int>>ans;
bool sol(int x)
{
for(int i=1;i<n;i++)
{
int maxx=*prev(s.end());
s.erase(s.find(maxx));
if(s.find(x-maxx)!=s.end())
{
s.erase(s.find(x-maxx));
ans.push_back({maxx,x-maxx});
x=maxx;
}
else break;
}
return ans.size()==n;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
cin>>t;
while(t--)
{
cin>>n;
m=2*n;flag=0;
for(int i=1;i<=m;i++) cin>>a[i];
sort(a+1,a+m+1);
for(int i=1;i<m;i++)
{
s.clear();ans.clear();
for(int j=1;j<m;j++)
{
if(j!=i) s.insert(a[j]);
}
ans.push_back({a[m],a[i]});
if(sol(a[m])){flag=1;break;}
}
if(flag)
{
cout<<"YESn";
cout<<ans[0].first+ans[0].second<<endl;
for(auto [x,y]:ans) cout<<x<<" "<<y<<endl;
}
else cout<<"NOn";
}
return 0;
}
//
/*
11
000100001000
*/

D - Assumption is All You Need 构造

大的数只能往右走，小的数只能往左走，每次交换较大的两个数，直到较大数回到正确的位置，然后次大数再继续走，这样会留出更多的机会给后面的数，也就是每次枚举大数往下走

D. Assumption is All You Need_chmpy的博客-CSDN博客

#include <bits/stdc++.h>
using namespace std;
#define endl 'n'
#define int long long
const int N = 3e5+5;
const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int t,n,a[2025],b[2035],posa[2035],posb[2035];
vector<pair<int,int>>ans;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
cin>>t;
while(t--)
{
ans.clear();
cin>>n;
int flag=1;
for(int i=1;i<=n;i++) cin>>a[i],posa[a[i]]=i;
for(int i=1;i<=n;i++) cin>>b[i],posb[b[i]]=i;
for(int i=n;i>=1;i--)
{
for(int j=i-1;j>=1;j--)
{
if(posa[j]>posa[i]&&posa[j]<=posb[i])
{
ans.push_back({posa[i],posa[j]});
swap(a[posa[i]],a[posa[j]]);
swap(posa[i],posa[j]);
}
}
if(posa[i]!=posb[i])
{
flag=0;break;
}
}
if(!flag) cout<<"-1n";
else
{
cout<<ans.size()<<endl;
for(auto [x,y]:ans) cout<<x<<" "<<y<<endl;
}
}
return 0;
}
//