令人闻风丧胆的NEERC——被称为ICPC题目质量之最的比赛，究竟是怎样的难度
令人闻风丧胆的NEERC——被称为ICPC题目质量之最的比赛，究竟是怎样的难度
ACM算法日常
发布于 2021-09-28 16:25:25
发布于 2021-09-28 16:25:25
代码可运行
运行总次数：0
代码可运行
NEERC，ACM-ICPC Northeastern European Regional Contest，是欧洲地区的异常区域赛，因其题目质量高而闻名于ICPC。
今天我们来看一套比较早的的 NEERC ，2015年的NEERC。
Problem A. Adjustment Office
显然假设每一行都没有进行过删除的话，那么答案就
的和
（
为行号或者列号）
考虑进行过清零以后的问题，由于是整行整列的删除的
那么我们只需要分别记录删除的行号和列号的总和，以及删掉的数量，然后就可以
得到了结果了
当然，别忘了开两个数组分别记录行和列有没有删除过
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='R' || x=='C');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m,r[1000010],c[1000010];
LL rnum,cnum,rsum,csum;
int main()
{
freopen("adjustment.in","r",stdin);
freopen("adjustment.out","w",stdout);
read(n);read(m);
char ch;rnum=cnum=rsum=csum=0;LL s=0,x;
memset(r,0,sizeof(r));
memset(c,0,sizeof(c));
while (m--)
{
read(ch);read(x);
if (ch=='R')
{
if (r[x]==0)
{
s=(1LL+(LL)n)*(LL)n/2LL-csum+(n-cnum)*x;
print(s),puts("");
rnum++,rsum+=x;r[x]=1;
}
else print(0),puts("");
}
else
{
if (c[x]==0)
{
s=(1LL+(LL)n)*(LL)n/2LL-rsum+(n-rnum)*x;
print(s),puts("");
cnum++,csum+=x;c[x]=1;
}
else print(0),puts("");
}
}
return 0;
}
Problem B. Binary vs Decimal
一个性质：
的二进制表示的末尾一定恰有
个
这样就可以枚举答案的位数，从低到高一位一位添加
,维护当前二进制末尾k位都合法的数字集合，因为有上面那个性质，所以从低到高枚举的时候，当把一个数十进制第
位赋为
的时候，只会影响到这个数二进制中第
位之前的值
因此，这个数的二进制后k位就逐一确定了，就可以把所有答案从小到大枚举出来。要用高精度。 复杂度
,
为答案的位数
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='?' || x=='+' || x=='-');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n;
struct data
{
int a[1000];
int flag;
}a[10010];
inline void print(data x)
{
int i=999;
while (x.a[i]==0) i--;
for (;i>=1;i--)
print(x.a[i]);
puts("");
}
data calc(int x)
{
int s=0;data y;
memset(y.a,0,sizeof(y.a));
while (x!=0) y.a[++s]=x%2,x/=2;
return y;
}
bool check(int x,int y)
{
int b[1000];
memset(b,0,sizeof(b));
int len=x;
for (int i=1;i<=len;i++)
b[i]=a[y].a[i];
b[x]=1;len=x;
for (int X=1;X<x;X++)
{
if (b[1]%2==1) b[1]--;
int z=0,p;
for (int i=len;i>=1;i--)
{
p=(z*10+b[i])%2;
b[i]=(z*10+b[i])/2;
z=p;
}
while (b[len]==0) len--;
}
if (b[1]%2==0) return false;
else return true;
}
int main()
{
freopen("binary.in","r",stdin);
freopen("binary.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++)
memset(a[i].a,0,sizeof(a[i].a));
for (int i=1;i<=7;i++)
a[i]=calc(i),a[i].flag=0;
if (n<=7) {print(a[n]);return 0;}
n-=7;int l=-1,r=7,i=4,s=7;a[0].flag=0;
while (n>0)
{
l++;
if (l>r) l=0,r=s,i++;
if (a[l].flag) continue;
if (check(i,l)) n--,s++,a[s]=a[l],a[s].a[i]=1;
else a[l].flag=1;
}
print(a[s]);
return 0;
}
Problem D. Distance on Triangulation
由于给出的图是一个多边形的三角剖分，因此每条对角线都能将这个多边形分成两个部分，就可以采用分治的方法。
类似树分治，先构出一个分治结构：每次在当前多边形中选出一条对角线，使得两部分点数尽可能均匀(可以证明最坏情况下存在任意一侧不少于n/3的分法）。
这条对角线两侧就形成了两个子多边形，递归下去，直到当前多边形为三角形为止，并且通过bfs计算出每个子多边形上每个点到选定的对角线两点的距离。
询问的时候只要判断一下两个点是否在选定的对角线同侧，如果是则递归求解，否则可以通过之前预处理出的距离简单计算。
复杂度
这道题目说起来容易，写起来还是很困难的。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='?' || x=='+' || x=='-');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m,ans[120010],d[60010];
struct data
{
int x,y,id;
data(int a,int b,int c=0):x(a),y(b),id(c){}
};
#define vd vector<data>
#define si set<int>
vd a,Q;
int op[60010],oppoppo;
vector<int> b[60010];
bool v[60010];
queue<int> q;
void solve(vd X,vd Y,int s,si P)
{
if (X.size()==3)
{
for (int i=0;i<Y.size();i++)
ans[Y[i].id]=1;
return ;
}
oppoppo++;
int Max=0,w=0,x,y;
for (int i=0;i<X.size();i++)
{
x=max(X[i].x,X[i].y),y=min(X[i].x,X[i].y);
x=min(op[x]-op[y],s-op[x]+op[y]);
if (x>Max) Max=x,w=i;
}
x=min(X[w].x,X[w].y),y=max(X[w].x,X[w].y);
vd qx,qy;
int point1[60010],point2[60010];
si PX,PY;PX.clear();PY.clear();
for (int i=0;i<X.size();i++)
{
if (X[i].x==x && X[i].y==y || X[i].x==y && X[i].y==x) qx.push_back(X[i]),qy.push_back(X[i]),
point1[X[i].x]=oppoppo,point1[X[i].y]=oppoppo,point2[X[i].x]=oppoppo,point2[X[i].y]=oppoppo,
PX.insert(X[i].x),PX.insert(X[i].y),PY.insert(X[i].x),PY.insert(X[i].y);
else
{
if (X[i].x>=x && X[i].y>=x && X[i].x<=y && X[i].y<=y) qx.push_back(X[i]),point1[X[i].x]=oppoppo,point1[X[i].y]=oppoppo,PX.insert(X[i].x),PX.insert(X[i].y);
else qy.push_back(X[i]),point2[X[i].x]=oppoppo,point2[X[i].y]=oppoppo,PY.insert(X[i].x),PY.insert(X[i].y);
}
}
vd q1,q2,q3;
for (int i=0;i<Y.size();i++)
if (Y[i].x==x && Y[i].y==y || Y[i].x==y && Y[i].y==x) ans[Y[i].id]=1;
else
{
if (Y[i].x>=x && Y[i].y>=x && Y[i].x<=y && Y[i].y<=y) q1.push_back(Y[i]);
else if ((Y[i].x<=x || Y[i].x>=y) && (Y[i].y<=x || Y[i].y>=y)) q2.push_back(Y[i]);
else q3.push_back(Y[i]);
}
for (int i=0;i<X.size();i++)
{
if (b[X[i].x].size()>0) b[X[i].x].clear();
if (b[X[i].y].size()>0) b[X[i].y].clear();
}
for (int i=0;i<X.size();i++)
b[X[i].x].push_back(X[i].y),b[X[i].y].push_back(X[i].x);
memset(v,false,sizeof(v));
q.push(y);
d[y]=0;
while (!q.empty())
{
int z=q.front();q.pop();
for (int i=0;i<b[z].size();i++)
if (!v[b[z][i]]) d[b[z][i]]=d[z]+1,q.push(b[z][i]),v[b[z][i]]=true;
}
for (int i=0;i<q3.size();i++)
ans[q3[i].id]=d[q3[i].x]+d[q3[i].y];
y=x;
memset(v,false,sizeof(v));
q.push(y);
d[y]=0;
while (!q.empty())
{
int z=q.front();q.pop();
for (int i=0;i<b[z].size();i++)
if (!v[b[z][i]]) d[b[z][i]]=d[z]+1,q.push(b[z][i]),v[b[z][i]]=true;
}
for (int i=0;i<q3.size();i++)
ans[q3[i].id]=min(ans[q3[i].id],d[q3[i].x]+d[q3[i].y]);
int opp=0;int NOW=oppoppo;
set<int>::iterator iter=P.begin();
while(iter!=P.end())
{
if (point1[*iter]==NOW) op[*iter]=++opp;
++iter;
}
solve(qx,q1,opp,PX);
opp=0;
iter=P.begin();
while(iter!=P.end())
{
if (point2[*iter]==NOW) op[*iter]=++opp;
++iter;
}
solve(qy,q2,opp,PY);
}
int main()
{
freopen("distance.in","r",stdin);
freopen("distance.out","w",stdout);
read(n);
int x,y;
for (int i=1;i<=n-3;i++)
read(x),read(y),a.push_back(data(x,y));
for (int i=1;i<n;i++)
a.push_back(data(i,i+1)),op[i]=i;op[n]=n;
a.push_back(data(n,1));
read(m);
for (int i=1;i<=m;i++)
{
read(x),read(y);
if (x==y) ans[i]=0;
else Q.push_back(data(x,y,i));
}
si X;
for (int i=1;i<=n;i++)
X.insert(i);
oppoppo=0;
solve(a,Q,n,X);
for (int i=1;i<=m;i++)
print(ans[i]),puts("");
return 0;
}
Problem E. Easy Problemset
感觉这道题目才是货真价实的签到题啊？
怎么cf上A比E过的人多呢......一定是E的题目太长...不太有人愿意读啊
直接按照题目意思模拟即可，不多说
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='R' || x=='C');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m,a[20][20];
void Next(int &x,int &y)
{
x++;
if (x>n) x=1,y++;
}
int main()
{
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
read(n);read(m);
for (int i=1;i<=n;i++)
{
read(a[i][0]);
for (int j=1;j<=a[i][0];j++)
read(a[i][j]);
}
int i=1,j=1,s=0;a[1][a[1][0]+1]=INT_MAX;
while (m!=0)
{
if (j<=a[i][0] && a[i][j]<s) {Next(i,j);continue;}
if (j<=a[i][0]) s+=a[i][j];else s+=50;
m--;
Next(i,j);
}
print(s);puts("");
return 0;
}
Problem F. Froggy Ford
显然，最有的情况下，添加的一个点一定是某两个点的终点那么两两之间连两条边，一条为原来的边，另一条为中间有点的边，第一条的权值为两点距离，第二条的权值为两点距离的一半然后限定，从起点到终点的最短路只能跑一次第二条边这类边
然后就是最短路了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
using namespace std;
int m,answ[1010][2];
double n,ans[1010][2];
struct data
{
double val;int x,z;
data(double a=0.0,double b=0.0,int c=0):x(a),val(b),z(c){}
};
vector <data> b[1010];
bool v[1010][2];
struct point
{
double x,y;
}a[1010];
struct Q
{
int x,y;
Q(int a=0,int b=0):x(a),y(b){}
};
queue<Q> q;
double dist(point x,point y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
int main()
{
freopen("froggy.in","r",stdin);
freopen("froggy.out","w",stdout);
scanf("%lf%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
for (int i=1;i<=m;i++)
b[0].push_back(data(i,a[i].x,0)),b[0].push_back(data(i,a[i].x/2.0,1)),
b[i].push_back(data(m+1,n-a[i].x,0)),b[i].push_back(data(m+1,(n-a[i].x)/2.0,1));
for (int i=1;i<=m;i++)
for (int j=i+1;j<=m;j++)
{
double x=dist(a[i],a[j]);
b[i].push_back(data(j,x,0)),b[i].push_back(data(j,x/2.0,1));
b[j].push_back(data(i,x,0)),b[j].push_back(data(i,x/2.0,1));
}
for (int i=1;i<=m+1;i++)
ans[i][0]=(1e9)*2.0,ans[i][1]=(1e9)*2.0;
ans[0][0]=0;ans[0][1]=(1e9)*2.0;
memset(v,false,sizeof(v));
q.push(Q(0,0));
v[0][0]=true;
while (!q.empty())
{
int x=q.front().x,y=q.front().y;q.pop();v[x][y]=false;
for (int i=0;i<b[x].size();i++)
if (y==0)
{
if (b[x][i].z==0)
{
if (ans[b[x][i].x][0]>max(ans[x][0],b[x][i].val))
{
ans[b[x][i].x][0]=max(ans[x][0],b[x][i].val);
if (!v[b[x][i].x][0]) q.push(Q(b[x][i].x,0)),v[b[x][i].x][0]=true;
}
}
else
{
if (ans[b[x][i].x][1]>max(ans[x][0],b[x][i].val))
{
answ[b[x][i].x][0]=x,answ[b[x][i].x][1]=b[x][i].x,ans[b[x][i].x][1]=max(ans[x][0],b[x][i].val);
if (!v[b[x][i].x][1]) q.push(Q(b[x][i].x,1)),v[b[x][i].x][1]=true;
}
}
}
else if (b[x][i].z==0)
{
if (ans[b[x][i].x][1]>max(ans[x][1],b[x][i].val))
{
answ[b[x][i].x][0]=answ[x][0],answ[b[x][i].x][1]=answ[x][1],ans[b[x][i].x][1]=max(ans[x][1],b[x][i].val);
if (!v[b[x][i].x][1]) q.push(Q(b[x][i].x,1)),v[b[x][i].x][1]=true;
}
}
}
double ansx,ansy;
if (answ[m+1][0]==0)
{
ansx=a[answ[m+1][1]].x/2.0;
ansy=a[answ[m+1][1]].y;
}
else if (answ[m+1][1]==m+1)
{
ansx=(a[answ[m+1][0]].x+n)/2.0;
ansy=a[answ[m+1][0]].y;
}
else
{
ansx=(a[answ[m+1][0]].x+a[answ[m+1][1]].x)/2.0;
ansy=(a[answ[m+1][0]].y+a[answ[m+1][1]].y)/2.0;
}
printf("%0.1lf %0.1lf\n",ansx,ansy);
return 0;
}
Problem G. Generators
发现c比较小，最坏情况下，循环节为c个
那么我们求出所有的循环节，那么最多一共有1e7个数，排个序
如果最大的和%m不为0，直接输出
否则，我们对于每一个数列，寻找最大的一个，满足
不为0的解，取最优的一个
如果仍然不存在，那么就无解了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='R' || x=='C');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m,c[1010];
struct data
{
int x,y;
}a[10010][1010];
bool cmp(data x,data y)
{
return x.x>y.x;
}
int main()
{
freopen("generators.in","r",stdin);
freopen("generators.out","w",stdout);
read(n);read(m);
int x,y,z;int ans=0;
for (int i=1;i<=n;i++)
{
memset(c,0,sizeof(c));
read(a[i][1].x);a[i][1].y=0;
c[a[i][1].x]=1;read(x);read(y);read(z);
int p=(x*a[i][1].x+y)%z,s=1;
while (c[p]==0) c[p]=1,a[i][++s].x=p,a[i][s].y=s-1,p=(x*p+y)%z;
sort(a[i]+1,a[i]+1+s,cmp);
ans+=a[i][1].x;
a[i][0].x=s;
}
if (ans%m==0)
{
int res,X,Y,Max=-1;
for (int i=1;i<=n;i++)
{
res=ans-a[i][1].x;
int j;
for (j=2;j<=a[i][0].x;j++)
if ((res+a[i][j].x)%m!=0) break;
if ((res+a[i][j].x)%m!=0 && j<=a[i][0].x)
{
res+=a[i][j].x;
if (res>Max) Max=res,X=i,Y=a[i][j].y;
}
}
if (Max==-1) print(Max),puts("");
else
{
print(Max);puts("");
for (int i=1;i<n;i++)
if (i!=X) print(a[i][1].y),putchar(' ');else print(Y),putchar(' ');
if (n!=X) print(a[n][1].y);else print(Y);
puts("");
}
}
else
{
print(ans);puts("");
for (int i=1;i<n;i++)
print(a[i][1].y),putchar(' ');
print(a[n][1].y),puts("");
}
return 0;
}
Problem J. Jump
好像可以先随便猜一个n / 2位相同的串出来..期望次数大约是40..
现在我们想知道每一位具体的值。 似乎将每一位单独取反之后.. 答案要么+1要么-1.. 返回值都是0
这样就没有办法判断了
把每位与第一位同时取反,然后做一次询问，这样就能得到每一位和第一位之间的关系了,这一步要进行n - 1次询问
然后枚举第一位是0还是1.. 根据之前得到的每位与第一位之间的关系，就能得出每一位的值。
对这两种情况分别做一次询问就好了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<ctime>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='R' || x=='C');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,a[2000],b[2000],m;
int main()
{
srand(time(0));
cin>>n;
while (1)
{
for (int i=1;i<=n;i++) (a[i]=rand())%=2,cout<<a[i];
cout<<endl;cin>>m;
if (m+m==n) break;
}
b[1]=a[1];
for (int i=2;i<=n;i++)
{
cout<<1-a[1];
for (int j=2;j<=i-1;j++) cout<<a[j];
cout<<1-a[i];
for (int j=i+1;j<=n;j++) cout<<a[j];
cout<<endl;cin>>m;
if (n==m+m) b[i]=1-a[i];
else b[i]=a[i];
}
for (int i=1;i<=n;i++) cout<<b[i];
cout<<endl;cin>>m;
if (m==n) return 0;
for (int i=1;i<=n;i++) cout<<1-b[i];
cout<<endl;
return 0;
}
Problem K. King’s Inspection
众所周知，哈密顿回路是一个NPC问题
那这道题目的突破口就在于边数小于等于点数+10
那么，也就是说，图中有大量的点是呈链状分布的，也就是说，我们可以把链所在一起
首先把入度和出度均为1的点，相连通的全部所谓一个点，那么剩下的点，在图中直接跑dfs即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='R' || x=='C');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m,s,flag,ru[100010],chu[100010],b[100010],ans[100010];
struct data
{
int l,r,s;
}a[100010];
bool v[100010];
vector<int > c[100010];
void dfs(int x)
{
//if (x==33082)
// print(x);
v[x]=true;
if (c[x].size()==1 && ru[x]==1)
{
a[s].r=x;a[s].s++;
if (!v[c[x][0]]) dfs(c[x][0]);
}
else
{
for (int i=0;i<c[x].size();i++)
{
if (chu[c[x][i]]==1 && ru[c[x][i]]==1 && !v[c[x][i]])
{
s++;a[s].l=c[x][i];dfs(c[x][i]);
}
else if (!v[c[x][i]]) dfs(c[x][i]);
}
}
}
bool check(int x,int y)
{
if (x<0) x=a[-x].l;
if (y<0) y=a[-y].r;
for (int i=0;i<c[y].size();i++)
if (c[y][i]==x) return true;
return false;
}
void WRITE(int x,int y)
{
if (x==y) {print(x),putchar(' ');return ;}
else print(x),putchar(' '),WRITE(c[x][0],y);
}
void write(int S)
{
for (int i=1;i<=S;i++)
if (ans[i]>0)
{
print(ans[i]),putchar(' ');
}
else WRITE(a[-ans[i]].l,a[-ans[i]].r);
print(1);
puts("");
}
void solve(int x,int y,int s)
{
//if (x==50419)
//print(1);
if (flag==1) return ;
if (y==n)
{
if (check(ans[1],ans[s])) write(s),flag=1;
return ;
}
//if (x==50419)
//print(1);
//if (x==55518)
// print(2);
for (int i=0;i<c[x].size();i++)
if (!v[c[x][i]])
{
int z=c[x][i];
v[x]=true;
if (b[z])
{
ans[s+1]=-b[z];
solve(a[b[z]].r,y+a[b[z]].s,s+1);
}
else
{
ans[s+1]=z;
solve(z,y+1,s+1);
}
v[x]=false;
}
}
int main()
{
freopen("king.in","r",stdin);
freopen("king.out","w",stdout);
read(n);read(m);
int x,y;
for (int i=1;i<=m;i++)
{
read(x);read(y);
if (x!=y)
{
chu[x]++;ru[y]++;
c[x].push_back(y);
}
}
memset(v,false,sizeof(v));
s=0;
if (chu[1]==1) {a[++s].l=1;}
dfs(1);
for (int i=1;i<=n;i++)
if (!v[i]) {puts("There is no route, Karl!");return 0;}
memset(b,0,sizeof(b));
for (int i=1;i<=s;i++)
b[a[i].l]=i,b[a[i].r]=i;
memset(v,false,sizeof(v));
flag=0;
if (b[1]) ans[1]=-b[1],solve(a[b[1]].r,a[b[1]].s,1);
else ans[1]=1,solve(1,1,1);
if (flag==0) puts("There is no route, Karl!");
return 0;
}
Problem L. Landscape Improved
二分答案
暴力枚举答案所在的列，剩下的问题就是验证答案了
首先我们发现，最后的形状一定是金字塔形的
那么，我们可以直接用优先队列大力预处理一发
然后根据预处理出的左边界和右边界，直接O（1）计算得到所需要的砖块，和n比较，得到可不可行即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<ctime>
#include<queue>
#define LL long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x=='R' || x=='C');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int m,p[100010],q[100010];
LL n,a[100010],sum[100010];
struct data
{
LL h;int x;
data(int a=0,LL b=0):x(a),h(b){}
};
struct cmp
{
bool operator()(data x,data y)
{
return x.h<y.h;
}
};
priority_queue<data,vector<data>,cmp> Q;
bool check(LL x)
{
while (!Q.empty()) Q.pop();
p[1]=0;int y=0;LL s=0;
Q.push(data(1,a[1]));
for (int i=2;i<=m;i++)
{
s++;LL z=Q.top().h;
while (z+s>=x)
{
y=max(y,Q.top().x);
Q.pop();
if (Q.empty()) break;
z=Q.top().h;
}
p[i]=y;
Q.push(data(i,a[i]-s));
}
while (!Q.empty()) Q.pop();
q[m]=m+1;y=m+1;s=0;
Q.push(data(m,a[m]));
for (int i=m-1;i>=1;i--)
{
s++;LL z=Q.top().h;
while (z+s>=x)
{
y=min(y,Q.top().x);
Q.pop();
if (Q.empty()) break;
z=Q.top().h;
}
q[i]=y;
Q.push(data(i,a[i]-s));
}
LL res;
for (int i=1;i<=m;i++)
if (p[i]!=0 && q[i]!=m+1)
{
res=(x+(x-(i-p[i])))*(i-p[i]+1)/2+(x+(x-(q[i]-i)))*(q[i]-i+1)/2-x-(sum[q[i]]-sum[p[i]-1]);
if (res<=n) return true;
}
return false;
}
int main()
{
freopen("landscape.in","r",stdin);
freopen("landscape.out","w",stdout);
read(m);read(n);
sum[0]=0;
LL l=1,r=n+((LL)(1e9)),res=-1,mid;
for (int i=1;i<=m;i++)
read(a[i]),sum[i]=sum[i-1]+a[i],l=max(l,a[i]);
res=l;
while (l<=r)
{
mid=l+r>>1;
if (check(mid)) l=mid+1,res=mid;
else r=mid-1;
}
print(res),puts("");
return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-09-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
