The 2018 ICPC Asia Nanjing Regional Contest [Cloned]
The 2018 ICPC Asia Nanjing Regional Contest [Cloned]
A-Adrien and Austin
题意：
给了你n个石子，编号从1到n，玩家要取最少一个最多k个连续编号的石子，求是先手赢，还是后手赢（不能操作即为输）
solution：
1、k==1时，判奇偶
2、k>1时，n<3时，此时n<=k必定成立，先手必胜，n>=3时，将n个石子从中间取几个，使其两边变成完全一样的两堆，此时先手必胜。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
int n,k;
int main()
{
scanf("%d%d",&n,&k);
if(n==0)printf("Austin");
else if(k==1)
{
if(n%2)printf("Adrien");
else printf("Austin");
}
else
printf("Adrien");
return 0;
}
B-Tournament
C-Cherry and Chocolate
D-Country Meow
E-Eva and Euro coins
F-Frank
G-Pyramid
题意：
给你n层的的三角形，求正三角形个数
solution：
打表找规律，把每个点的坐标存进去，然后跑一边n^3求正三角形个数
打表代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
struct node
{
double x,y;
}p[10005];
int cnt=0;
int main()
{
p[cnt].x=0;p[cnt].y=0;cnt++;
for(int i=1;i<=20;i++)
{
double pos=-i;
for(int j=1;j<=i+1;j++)
{
p[cnt].x=pos;
p[cnt].y=-i*sqrt(3);
pos+=2;
cnt++;
}
int c=0;
for(int j=0;j<cnt;j++)
{
for(int k=j+1;k<cnt;k++)
{
for(int w=k+1;w<cnt;w++)
{
double l1=(p[j].x-p[k].x)*(p[j].x-p[k].x)+(p[j].y-p[k].y)*(p[j].y-p[k].y);
double l2=(p[j].x-p[w].x)*(p[j].x-p[w].x)+(p[j].y-p[w].y)*(p[j].y-p[w].y);
double l3=(p[w].x-p[k].x)*(p[w].x-p[k].x)+(p[w].y-p[k].y)*(p[w].y-p[k].y);
//cout<<l1<<' '<<l2<<' '<<l3<<endl;
if(fabs(l1-l2)<1e-6&&fabs(l2-l3)<1e-6)c++;
}
}
}
printf("%d\n",c);
}
return 0;
}
然后找出C(n+3,4)求组合数的规律
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int t;
ll n;
const int mod=1e9+7;
ll fpow()
{
ll a=24,ans=1;
ll ti=mod-2;
while(ti)
{
if(ti%2)ans=ans*a%mod;
a=a*a%mod;
ti/=2;
}
return ans;
}
int main()
{
scanf("%d",&t);
ll inv24=fpow();
while(t--)
{
scanf("%lld",&n);
n+=3;
ll res=0;
res=n*(n-1)%mod*(n-2)%mod*(n-3)%mod*inv24%mod;
printf("%lld\n",res);
}
}
H-Huge Discount
I- Magic Potion
题意：
给了n个heros，m个monsters，以及k个potion
每个英雄能杀死一个怪兽，用了potion后英雄能多杀一只怪兽（每个英雄只能用一次potion）
给了你n个集合，第i个集合里有ti个数，对应当前第i个英雄所能杀的怪兽的编号
问最多能杀多少只怪兽。
solution：
二分图最大匹配or网络流dinic
网络流dinic做法
给每个人和所杀怪兽之间连边，k个option与人连边，建立超级源点、超级终点
3 5 2
4 1 2 3 5
2 2 5
2 1 2
5 10 2
2 3 10
5 1 3 4 6 10
5 3 4 6 8 9
3 1 9 10
5 1 3 6 7 10
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int n,m,k;
int head[200050];
int cur[200050];
int deep[200050];
int cnt;
int S,T;
struct Edge
{
int to,w,next;
}edge[400050];
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
void add_edge(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int dfs(int u,int flow)
{
if(u==T)return flow;
for(int& i=cur[u];i!=-1;i=edge[i].next)
{
if(deep[edge[i].to]==deep[u]+1&&edge[i].w!=0)
{
int d=dfs(edge[i].to,min(flow,edge[i].w));
if(d>0)
{
edge[i].w-=d;
edge[i^1].w+=d;
return d;
}
}
}
return 0;
}
int bfs()
{
queue<int> q;
while(!q.empty())q.pop();
memset(deep,0,sizeof(deep));
deep[S]=1;
q.push(S);
do
{
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
if(deep[edge[i].to]==0&&edge[i].w>0)
{
deep[edge[i].to]=deep[u]+1;
q.push(edge[i].to);
if(edge[i].to==T)return 1;
}
}
}while(!q.empty());
if(deep[T]>0)return 1;
return 0;
}
int Dinic()
{
int ans=0;
while(bfs())
{
for(int i=0;i<=T;i++)cur[i]=head[i];
while(int d=dfs(S,INF))
{
ans+=d;
}
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
init();
S=0;T=m+n+2;
int st=n+m+1;
add_edge(S,st,k);
add_edge(st,S,0);
for(int i=1;i<=n;i++)
{
add_edge(S,i,1);
add_edge(i,S,0);
add_edge(st,i,1);
add_edge(i,st,0);
int kk;scanf("%d",&kk);
for(int j=0;j<kk;j++)
{
int x;scanf("%d",&x);
add_edge(i,x+n,1);
add_edge(x+n,i,0);
}
}
for(int i=1;i<=m;i++)
{
add_edge(i+n,T,1);
add_edge(T,i+n,0);
}
printf("%d\n",Dinic());
}
J-Prime Game
题意：
求所有子区间内质因子个数和（子区间内相同的质因子算一个）
solution：
找规律，同一个质因子有一个对后面的贡献，以及前面没有出现该质因子是也会产生一个贡献，所以就是找规律求贡献
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int n,a[1000006];
vector<int> e[1000006];
int vis[1000006],prime[1000006],cnt=0;
int main()
{
vis[1]=1;
for(int i=2;i<=1000000;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
for(int j=i*2;j<=1000000;j+=i)
vis[j]=1;
}
}
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
int j=0;
while(a[i]>1)
{
if(a[i]%prime[j]==0)
{
if(e[prime[j]].size()==0)
e[prime[j]].push_back(-1);
e[prime[j]].push_back(i);
while(a[i]%prime[j]==0)
a[i]/=prime[j];
}
else if(!vis[a[i]])
{
if(e[a[i]].size()==0)
e[a[i]].push_back(-1);
e[a[i]].push_back(i);
a[i]=1;
}
j++;
}
}
ll res=0;
for(int i=0;i<cnt;i++)
{
for(int j=1;j<e[prime[i]].size();j++)
{
res+=1ll*(e[prime[i]][j]-e[prime[i]][j-1])*(n-e[prime[i]][j]);
//cout<<prime[i]<<' '<<res<<endl;
}
}
printf("%lld",res);
}
我现在也只有一个保底
太难了
