碎碎念
“大家好像都很哀伤”
“但为什么不能相互理解呢”
今天是edu场，4/7还是太弱了
E想出来了，就一个exgcd，板子还是网上摘的（
一个括号位置写错，赛后五分钟调出来的痛苦谁懂啊呜呜呜
A - Colored Balls: Revisited
给你一个数组，分别表示有a[i]个i，保证一共只有奇数个数
每次操作可以删去任意两个不同的数，求任意一个可能最后留下的数
solution
每次拉最少的两个删，显然最后留下的一定是最多的那个数
#include<bits/stdc++.h>
using namespace std;
int T,n,a[30];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>=a[ans])ans=i;
}
printf("%d\n",ans);
}
return 0;
}B - Best Permutation
定义一个排列的价值x：
初始x=0，i从1->n：
x<p[i]则x+=p[i]，否则x=0
构造一个排列使最后的价值x最大化
solution
显然最大的价值是(n-1)+n
有如下构造法：
n为偶数：2，1，4，3，……，n-2，n-3，n-1，n
n为奇数：1，3，2，5，4，……，n-2，n-3，n-1，n
#include<bits/stdc++.h>
using namespace std;
int T,n;
int main()
{
// 2,1,4,3,...,n-1,n
// 1,3,2,5,4,...,n-1,n
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
if(n%2)
{
putchar('1'),putchar(' ');
for(int i=2;i<=n-2;i+=2)
printf("%d %d ",i+1,i);
printf("%d %d\n",n-1,n);
}
else
{
for(int i=1;i<=n-2;i+=2)
printf("%d %d ",i+1,i);
printf("%d %d\n",n-1,n);
}
}
return 0;
}C - Digital Logarithm
给你两个集合，每次可以对任一集合中任一元素执行一次如下操作：
将x变为x的位数，询问最少几次操作可以让两个集合相同
solution
显然一个数做一次操作变成一位数，两次操作一定是1
先将所有已经相同的数删去，再将所有非一位数执行一次操作
再将所有已经相同的数删去，剩下每个数执行一次操作
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int T,n,a[200010],b[200010];
int calc(int x)
{
int p=0;
while(x)
x/=10,p++;
return p;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(b+1,b+1+n);
int p=1,ans=0;
for(int i=1;i<=n;i++)
{
while(p<n&&b[p]<a[i])p++;
if(p<=n&&b[p]==a[i])
a[i]=inf,b[p]=inf,p++;
}
for(int i=1;i<=n;i++)
{
if(a[i]>=10&&a[i]!=inf)
a[i]=calc(a[i]),ans++;
if(b[i]>=10&&b[i]!=inf)
b[i]=calc(b[i]),ans++;
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
p=1;
for(int i=1;i<=n;i++)
{
while(p<n&&b[p]<a[i])p++;
if(p<=n&&b[p]==a[i]&&a[i]!=inf)
a[i]=inf,b[p]=inf,p++;
}
for(int i=1;i<=n;i++)
{
if(a[i]!=inf&&a[i]!=1)ans++;
if(b[i]!=inf&&b[i]!=1)ans++;
}
printf("%d\n",ans);
}
return 0;
}D - Letter Picking
两个人玩游戏，现有一个公共字符串，同时每个人各有一个空的字符串，轮流取字符：
每次可以取公共字符串头或尾的字符加到自己字符串的头，最后字符串字典序小的获胜
两个人都足够理智的情况下求出最终结果
solution
这个游戏吧，显然...后手是不胜的，所以先手奔着胜利，后手奔着平局
那么先手只需要取一个后手无法取相同的，就获胜了
所以先取头尾相同的，再取两个连着相同的，如果有取不了的，先手必胜，否则平局
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int T,n;
char s[2010];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
n=strlen(s);
int l=0,r=n-1;
while(s[l]==s[r]&&l<=r)
l++,r--;
while(s[l]==s[l+1]&&l<=r)
l+=2;
if(l<=r)puts("Alice");
else puts("Draw");
}
return 0;
}E - Red-Black Pepper
n道菜，m个商店，现有两种调味料
每道菜只能用一种调味料，用1号则获得a[i]价值，2号获得b[i]价值
每个商店都无限打包售卖两种调味料，一包有x[i]种1号或y[i]种2号
对于每一个商店询问刚好用完所有调味料的情况下所能获得的最大价值
solution
因为要刚好用完所有调味料，所以这是一个解二元一次方程的问题，需要exgcd
然后思考如何调整这个方程的解，一开始全部用1号调味料，开一个数组c存b[i]-a[i]
将c排序之后显然从大往小取最优，最优的是刚好把所有正数取完
找到第一个负数所在的位置，暴力判断附近的十组解就可以了
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Exgcd(int a,int b,int &x,int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}
int n,m,x,y,a[300010];
int s,ss[300010];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&x,&y),
s+=x,a[i]=y-x;
sort(a+1,a+1+n);
for(int i=n;i>=1;i--)
ss[i]=a[i]+ss[i+1];
int p1;
for(int i=1;i<=n+1;i++)
if(a[i]>=0){p1=i;break;}
p1=n-p1+1;
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
int l,r,lx,ry,p=Exgcd(x,y,l,r);
if(n%p){puts("-1");continue;}
l*=n/p,r*=n/p;
lx=y/p,ry=x/p;
if(l<0)
{
r-=ry*((-l+lx-1)/lx);
l+=lx*((-l+lx-1)/lx);
}
if(r<0)
{
l-=lx*((-r+ry-1)/ry);
r+=ry*((-r+ry-1)/ry);
}
if(l<0||r<0){puts("-1");continue;}
int ret=r*y,lcm=x/p*y;
int ans=0;
for(int j=-5;j<=5;j++)
{
int rett=ret+((p1-ret)/lcm+j)*lcm;
if(rett<0||rett>n)continue;
ans=max(ans,s+ss[n-rett+1]);
}
printf("%lld\n",ans);
}
return 0;
}
Comments NOTHING