比赛地址
Pro: 3/3/10
Rank: 159/906
[A] Permutation
题意
给出一个质数p,要求找到一个1到p-1的排列,使得排列的后一项和前一项的两倍同余,或者和前一项的三倍同余.
题解
直接从1开始构造,先按照倍数2构造,不行的话就按倍数3构造.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int used[1000005], ans[1000005];
int main(){
int T; scanf("%d", &T);
for (int t = 1; t <= T; t++) {
int n; scanf("%d", &n);
if (n == 2) {
printf("1\n");
continue;
} else if (n == 3) {
printf("1 2\n");
continue;
}
int now = 1, tot = 0;
ans[++tot] = now; used[1] = t;
for (int i = 1; i < n; i++) {
if (used[now*2%n]==t) {
if (used[now*3%n]==t) break;
now = now * 3 % n;
used[now] = t;
ans[++tot] = now;
} else {
now = now * 2 % n;
used[now] = t;
ans[++tot] = now;
}
}
if (tot != n-1) printf("-1");
else for (int i = 1; i <= tot; i++) printf("%d ", ans[i]);
printf("\n");
}
return 0;
}
[D] Hearthstone Battlegrounds
题意
题目背景为炉石的酒馆战棋.
两个完全体鱼人打团战,问一方能不能在完美团的情况下打赢对面.
和炉石的规则有一点不同,亡语只会掉落一个植物.
炉石传说真尼玛好玩
题解
按照完美团的情况直接模拟团战即可.
下面的写法比较暴力,将25种对撞的结果直接列举出来,按照收益从高到低排序,依次对撞.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T,i;
int a[15],b[15];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Work(){
reg int i=0,x=0,y=0,s=0,S=0;
for (i=1;i<=4;i++) s+=a[i];
for (i=1;i<=4;i++) S+=b[i];
a[5]=b[5]=0;
while (S && s){
/* cout<<s<<" "<<S<<endl;
cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<endl;
cout<<b[1]<<" "<<b[2]<<" "<<b[3]<<" "<<b[4]<<" "<<b[5]<<endl;
*/
if (b[5] && (a[3] || a[4])){
S-=b[5]; b[5]=0;
continue;
}
if (a[5] && b[1]){
x=Min(a[5],b[1]);
s-=x; a[5]-=x;
b[1]-=x; b[3]+=x;
continue;
}
if (a[5] && b[2]){
x=Min(a[5],b[2]);
s-=x; a[5]-=x;
b[2]-=x; b[4]+=x;
continue;
}
//1-1 -> ()
if (a[3]){
if (b[3]){
a[3]--; b[3]--;
a[5]++; b[5]++;
continue;
} else if (b[4]){
a[3]--; b[4]--;
a[5]++; S--;
continue;
}
}
if (a[3] && b[1]){
a[3]--; a[5]++;
b[1]--; b[3]++;
continue;
}
if (a[3] && b[2]){
a[3]--; a[5]++;
b[2]--; b[4]++;
continue;
}
if (a[1] && b[3]){
x=1;
a[1]-=x; a[3]+=x;
b[3]-=x; S-=x;
continue;
}
if (a[1] && b[4]){
x=1;
a[1]-=x; a[3]+=x;
b[4]-=x; S-=x;
continue;
}
if (a[1] && b[1]){
a[1]--; b[1]--;
a[3]++; b[3]++;
continue;
}
if (a[1] && b[2]){
a[1]--; b[2]--;
a[3]++; b[4]++;
continue;
}
if (a[2] && b[1]){
b[1]--; b[3]++;
a[2]--; a[4]++;
continue;
}
if (a[2] && b[2]){
a[2]--; b[2]--;
a[4]++; b[4]++;
continue;
}
if (a[2] && b[3]){
x=1;
a[2]-=x; a[4]+=x;
b[3]-=x; S-=x;
continue;
}
if (a[2] && b[4]){
x=1;
a[2]-=x; a[4]+=x;
b[4]-=x; S-=x;
continue;
}
if (a[4] && b[3]){
a[4]--; s--;
b[3]--; b[5]++;
continue;
}
if (a[4] && b[4]){
a[4]--; s--;
b[4]--; S--;
continue;
}
if (a[4] && b[1]){
a[4]--; s--;
b[1]--; b[3]++;
continue;
}
if (a[4] && b[2]){
a[4]--; s--;
b[2]--; b[4]++;
continue;
}
if (a[5] && b[5]){
x=Min(a[5],b[5]);
s-=x; S-=x;
a[5]-=x; b[5]-=x;
continue;
}
if (b[5] && a[1]){
a[1]--; a[3]++;
S-=b[5]; b[5]=0;
continue;
}
if (b[5] && a[2]){
a[2]--; a[4]++;
S-=b[5]; b[5]=0;
continue;
}
if (a[5] && (b[3] || b[4])){
s-=a[5]; a[5]=0;
continue;
}
}
if (s) puts("Yes");
else puts("No");
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
for (i=1;i<=4;i++) a[i]=read();
for (i=1;i<=4;i++) b[i]=read();
Work();
}
return 0;
}
[E] Game
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int T,i,n,low,high,mid,ans;
int a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL LL Min(LL a,LL b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL bool Check(int x){
reg int i=0;
LL res=0;
for (i=n;i;i--){
if (!res && a[i]<=x) continue;
if (a[i]>x) res+=a[i]-x;
if (a[i]<x) res-=Min(res,x-a[i]);
}
return (res<=0);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read();
for (i=1;i<=n;i++) a[i]=read();
if (n==1){
printf("%d\n",a[1]);
continue;
}
ans=0; low=1; high=INF;
while (low<=high){
mid=(low+high)>>1;
if (Check(mid)) ans=mid,high=mid-1;
else low=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
总结
二打三真的很难顶QAQ
前期一个重大失误就是,以为H题就是个简单的构造题,然后在上面浪费了过多的时间.在看到通过人数0/300+的时候就应该及时收手换题了.还有个问题就是,中期不太敢去开新题,盲目跟榜想J,但其实先做D是最优的.如果时间足够充裕的话,在做完D之后有机会推出B的.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第十场
本文地址: 2020牛客暑期多校第十场
