|
A
#include<bits/stdc++.h>
using namespace std;
const int maxn=10;
int f[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
for(int i=1;i<=7;i++)scanf("%d",&f[i]);
sort(f+1,f+8);
int a=f[1],b=f[2];
int c;
if(f[3]==a+b)c=f[4];
else c=f[3];
printf("%d %d %d\n",a,b,c);
}
}
B
#include<bits/stdc++.h>
using namespace std;
// const int maxn=10;
bool st[2];
char op[110][5];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
bool flag=false;
memset(st,false,sizeof(st));
memset(op,0,sizeof(op));
for(int i=1;i<=n-2;i++)
{
scanf("%s",op[i]+1);
if(i!=1&&op[i][1]!=op[i-1][2])
{
printf("%c",op[i-1][2]);
flag=true;
}
printf("%c",op[i][1]);
st[op[i][1]-'a']=true;
}
if(flag)
{
printf("%c\n",op[n-2][2]);
}
else
{
printf("%c",op[n-2][2]);
if(!st[0])printf("a\n");
else printf("b\n");
}
// cout<<1<<endl;
}
}
C gcd乱搞
#include<bits/stdc++.h>
#define int long long
using namespace std;
// const int maxn=10;
typedef long long ll;
ll a[117];
signed main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
if(n==2)
{
sort(a+1,a+3);
if(a[1]==a[2])printf("0\n");
else
printf("%lld\n",a[2]);
continue;
}
int d=a[1];
for(int i=1;i<=n;i+=2)
{
d=gcd(d,a[i]);
}
bool flag=false;
for(int i=2;i<=n;i+=2)
if(a[i]%d==0)
{
flag=true;
break;
}
bool flag2=false;
if(flag)
{
flag=true;
d=a[2];
for(int i=2;i<=n;i+=2)
d=__gcd(d,a[i]);
for(int i=1;i<=n;i+=2)
if(a[i]%d==0)
{
flag2=true;
break;
}
}
if(flag&&flag2)printf("0\n");
else printf("%lld\n",d);
}
}
D?
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int a[maxn];
bool st[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
int res=0;
for(int i=n-2*k+1;i<=n-k;i++)
{
res+=a[i]/a[i+k];
}
for(int i=1;i<n-2*k+1;i++)
res+=a[i];
printf("%d\n",res);
}
}
E
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int b[maxn];
int a[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
ll sum=0;
for(int i=1;i<=n;i++)sum+=b[i];
ll x=1ll*n*(n+1)/2;
if(sum%x)
{
printf("NO\n");
continue;
}
sum/=x;
bool flag=true;
for(int i=1;i<=n;i++)
{ a[i]=sum+b[(i+n-2)%(n)+1]-b[i];
if(a[i]<=0||a[i]%n)
{
flag=false;
break;
}
a[i]/=n;
}
if(!flag)
{
printf("NO\n");
}
else
{
printf("YES\n");
for(int i=1;i<=n;i++)printf("%d ",a[i]);
printf("\n");
}
}
}
F
当作字符串去做，可以发现最开始输入的数x可以转变为4个不同的01字符串str
并且str的begin和end都为1
然后仔细推测不难发现y必定是这四种可能在前面加有限个1，在后面加有限个1构成的
然后就暴力去做好了。
当然也可以bfs或dfs，那种剪枝的原理我感觉挺神奇的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> a,b;
bool get(vector<int> t)
{
for(int i=0;i<b.size();i++)
{
bool flag=true;
if(t.size()+i-1>=b.size())return false;
for(int j=0;j<t.size();j++)
if(b[i+j]!=t[j]){flag=false;break;}
if(!flag)continue;
for(int j=0;j<i;j++)if(b[j]==0){flag=false;break;}
for(int j=t.size()+i-1;j<b.size();j++)if(b[j]==0){flag=false;break;}
if(flag)return true;
}
return false;
}
bool check(vector<int> t)
{
if(get(t))return true;
reverse(t.begin(),t.end());
if(get(t))return true;
return false;
}
void solve()
{
a.push_back(1);
if(check(a)){printf("YES\n");return ;}
a.pop_back();
while(a.size()&&a.back()==0)a.pop_back();
if(check(a)){printf("YES\n");return ;}
printf("NO\n");return ;
}
int main()
{
ll x,y;
scanf("%lld%lld",&x,&y);
if(x==y){printf("YES");return 0;}
while(x)a.push_back(x%2),x/=2;
while(y)b.push_back(y%2),y/=2;
reverse(a.begin(),a.end());
reverse(b.begin(),b.begin());
solve();
}
G
这个构思是真的巧妙，用并查集做。
储存好a和b的初始id，然后把他们用pair合并之后排序。k'也按照升序排序。
每个a本身都有一个size，且size=1。
只有合并的时候会使得size可能增大（因为并不能保证两个集合里的size都>1）
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
typedef pair<int,int> pii;
pii query[maxn],a[maxn<<1];
ll ans[maxn<<1],sum[maxn<<1];
int p[maxn<<1];
int siz[maxn<<1];
map<int,vector<int>> mp;
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n+m;i++)scanf("%d",&a[i].x),a[i].y=i;
sort(a+1,a+n+m+1);
for(int i=1;i<=q;i++)scanf("%d",&query[i].x),query[i].y=i;
sort(query+1,query+q+1);
ll res=0;
for(int i=1;i<=n+m;i++)
{
siz[i]=(a[i].y<=n);
p[i]=i;
if(i>1)mp[a[i].x-a[i-1].x].push_back(i-1);
sum[i]=sum[i-1]+a[i].x;
if(a[i].y<=n)res+=a[i].x;
}
auto it=mp.begin();
for(int i=1;i<=q;i++)
{
if(query[i].x==query[i-1].x){ans[query[i].y]=res;continue;}
while(it!=mp.end()&&it->x<=query[i].x)
{
for(auto t:it->y)
{
int xi=find(t),yi=find(t+1);
res-=sum[xi]-sum[xi-siz[xi]]+sum[yi]-sum[yi-siz[yi]];
siz[yi]+=siz[xi],p[xi]=yi;
res+=sum[yi]-sum[yi-siz[yi]];
}
it++;
}
ans[query[i].y]=res;
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
}
|