Forethought Future Cup - Elimination Round
A：签到。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n;char s[100];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%s",s+1);n=strlen(s+1);int cnt=0;
for (int i=1;i<=n;i++) if (s[i]=='a') cnt++;
for (int i=n;i>=1;i--) if (cnt>i/2) {cout<<i;break;}
return 0;
//NOTICE LONG LONG!!!!!
}
B：显然可能的划分位置只有一个，找到后检验即可。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n;char s[N],a[N],b[N];
signed main()
{
scanf("%s",s+1);n=strlen(s+1);int cnt=0;
int cnt2=0;for (int i=1;i<=n;i++) if (s[i]=='a') cnt2++;
for (int i=1;i<=n;i++)
{
if (s[i]=='a') cnt++;
if (cnt==cnt2&&i-cnt==n-i)
{
int t=0;
for (int j=1;j<=i;j++) if (s[j]!='a') a[++t]=s[j];
t=0;
for (int j=i+1;j<=n;j++) b[++t]=s[j];
for (int j=1;j<=t;j++) if (a[j]!=b[j]) {cout<<":(";return 0;}
for (int j=1;j<=i;j++) putchar(s[j]);return 0;
}
}
cout<<":(";
return 0;
//NOTICE LONG LONG!!!!!
}
C：二进制分组。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int T,n,a[110],b[110];
signed main()
{
T=read();
while (T--)
{
n=read();
int ans=0;
for (int i=7;i>=0;i--)
{
int u=0,v=0;
for (int j=1;j<=n;j++)
if (j&(1<<i)) a[++u]=j;
else b[++v]=j;
if (u&&v)
{
cout<<u<<' '<<v<<' ';
for (int j=1;j<=u;j++) cout<<a[j]<<' ';
for (int j=1;j<=v;j++) cout<<b[j]<<' ';
cout<<endl;
ans=max(ans,read());
}
}
cout<<-1<<' '<<ans<<endl;
}
return 0;
//NOTICE LONG LONG!!!!!
}
D：不考虑范围限制的话显然能到达所有gcd(a,b)的倍数。注意到对于不小于a+b的gcd(a,b)的倍数，该点一定可以为到达该点时所经过的最大值。因为可以考虑每次若能往左走就往左走，否则往右走，显然这样往右走的时候所达位置一定<=a+b，且这样可以到达0~a中所有gcd(a,b)的倍数，由这些点一直向右就可以到达所有gcd(a,b)的倍数了。那么对于<a+b的数暴力跑dij，>=a+b的数等差数列求和即可。然后因为inf设小调了一年。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a,b,d[1000010];
bool flag[1000010];
struct data
{
int x,d;
bool operator <(const data&a) const
{
return d>a.d;
}
};
priority_queue<data> q;
void dij()
{
for (int i=1;i<=M;i++) d[i]=1000000000;d[0]=0;
q.push((data){0,0});
for (;;)
{
while (!q.empty()&&flag[q.top().x]) q.pop();
if (q.empty()) break;
data x=q.top();q.pop();
flag[x.x]=1;
if (x.x>=b&&d[x.x-b]>x.d)
{
d[x.x-b]=x.d;
q.push((data){x.x-b,d[x.x-b]});
}
if (x.x+a<=M&&d[x.x+a]>max(x.x+a,x.d))
{
d[x.x+a]=max(x.x+a,x.d);
q.push((data){x.x+a,d[x.x+a]});
}
}
}
signed main()
{
n=read(),a=read(),b=read();
dij();
ll ans=0;
for (int i=0;i<=min(n,M);i++) ans+=max(0,n-d[i]+1);
int u=gcd(a,b),cnt=n/u-M/u;
if (cnt>0)
{
ans+=1ll*cnt*(n+1);
int l,r;
for (l=M+1;l<=n;l++) if (l%u==0) break;
for (r=n;r>M;r--) if (r%u==0) break;
ans-=1ll*(l+r)*cnt/2;
}
//��i (i=1000001~n,i%u==0)
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
EFGH：占坑待填。
更多精彩
