2018 ICPC Asia Nanjing Regional Contest

solve: 5/13

Practice link:https://vjudge.net/contest/388613#overview

A - Adrien and Austin

题意：给你 n 个石头，编号从1~n，有两个人，每个人每次操作只能从石头中取 1~k 个连续编号的石头，最后不能取的一方为输，问谁会赢。

思路：先手必输状态：1、k==1且 n%2==0

                                    2、n==0

代码：

int main()
{
     int n,k;
     scanf("%d %d",&n,&k);
     if(n==0||(k==1&&n%2==0)){
       cout<<"Austin"<<endl;
     }else{
       cout<<"Adrien"<<endl;
     }
     return 0;
} 

D - Country Meow

题意：给你 n 个三维方向上的点，让你建立一个中心指挥部，使这个点到这些点的最大距离最短。

思路：模拟退火求最小球覆盖

代码：

#include<bits/stdc++.h>
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;const double eps=1e-7;
struct point3D
{
    double x,y,z;
} data[35];
ll n;
double dis(point3D a,point3D b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double solve()
{
    double step=100000,ans=1e30,mt;
    point3D z;
    z.x=z.y=z.z=0;
    ll s=0;
    while(step>eps)
    {
        for(int i=0; i<n; i++)
            if(dis(z,data[s])<dis(z,data[i])) s=i;
        mt=dis(z,data[s]);
        ans=min(ans,mt);
        z.x+=(data[s].x-z.x)/mt*step;
        z.y+=(data[s].y-z.y)/mt*step;
        z.z+=(data[s].z-z.z)/mt*step;
        step*=0.98;
    }
    return ans;
}
int main()
{ // freopen("t.txt","r",stdin);
    double ans;
    scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%lf%lf%lf",&data[i].x,&data[i].y,&data[i].z);
        ans=solve();
        printf("%.15f
",ans);
    return 0;
}

G - Pyramid

题意：如下图所示，给你一个边长为 n 的等边三角形，问你在这个三角形中有多少个等边三角形。

           

思路：打表找规律，可以推得 num = n*(n+1)*(n+2)*(n+3)/24，因为要取余操作且式子中有除法，因此要求24的逆元，再取余即可。

代码：

void extend_gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0) {
        x=1,y=0;
        return;
    }
    extend_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-(a/b)*y;
}
ll mod_inverse(ll a,ll m)
{
    ll x,y;
    extend_gcd(a,m,x,y);
    return (m+x%m)%m;
}
int main()
{    
   ll T,n;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        ll sum=1;
        for(int i=0;i<=3;i++)
        {
            sum=sum*(n+i)%Mod;
        }
        ll k=mod_inverse(24,Mod);
        sum=((sum%Mod)*(k%Mod))%Mod;
        printf("%lld
",sum);
    }
}

I - Magic Potion

题意：有 n 个英雄和 m 个怪兽，每个英雄有可以打到的怪兽的集合且每个英雄只能打一个怪兽。又有 k 瓶药，每个英雄至多用一瓶，一瓶药可以使一个英雄多打一个怪兽。问你最多有几个怪兽被打。

思路：这题可以看出是一道二分图最大匹配题，首先把一个英雄拆成两个点，每个点都与可以打的怪兽建边，求这个图的最大匹配 ans，然后不考虑有药的情况求二分图的最大匹配 ans2，接下来看条件，如果

 ans2+k<=ans，则输出 ans2+k，否则输出 ans 即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn = 1000005;
const int NUM = 1e4+5;
int n,m,k,flag,ans;
int link[NUM];
bool vis[NUM];
vector<int>g[4*NUM];
bool dfs(int x)
{
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!vis[v]){
            vis[v]=1;
            if(!link[v]||dfs(link[v])){
                link[v]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    ans=0;
    mem(link,0);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        for(int j=1;j<=t;j++){
            int x;
            scanf("%d",&x);
            g[i].push_back(2*n+x);
            g[n+i].push_back(2*n+x);
        }
    }
    for(int i=1;i<=2*n;i++){
        mem(vis,0);
        if(dfs(i))ans++;
    }
    int ans2=0;
    mem(link,0);
    for(int i=1;i<=n;i++){
        mem(vis,0);
        if(dfs(i))ans2++;
    }
        if(ans2+k<=ans){
            cout<<ans2+k<<endl;
        }else{
            cout<<ans<<endl;
        }
    return 0;
}

J - Prime Game

题意：给你 n 个数，定义    ， 为 的不同的质因数的个数。求 。

思路：应该考虑每个素数因子对答案的贡献，首先对于 第p个元素含有某个素数因子，则该元素对答案的贡献为 （ n - p + 1 )*p。接下来考虑有重复的情况出现，比如说 第 k 个元素（在p之前）也有某个素数因子，则该元素对答案的贡献为 （ n - k + 1 )*k，则第 p 个元素的贡献就变成了 （ n - p + 1 )*( p - k)。然后我们用 pos[ i ][ k ]储存素数因子 i 第 k 次出现的位置，那么我们只需要遍历每个素数因子 i 让sum=sum+ (n - pos[ i ][ k ] + 1)*( pos[ i ][ k ] - pos[ i ][ k - 1])即可，注意让 pos[ i ][ 0 ] = 0。

代码：

#include<bits/stdc++.h>
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn = 1000005;
const int NUM = 1e4+5;

int n,a[maxn];
vector<int>pos[maxn];
void dec(int p)
{
    int n=a[p];
    for(int i=2;i*i<=n;i++){
        if(n%i==0)
        {
            pos[i].push_back(p);
            while(n%i==0)n/=i;   //
        }
    }
    if(n>1)pos[n].push_back(p);
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=1000000;i++)pos[i].push_back(0);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        dec(i);
    }
    ll sum=0;
    for(int i=2;i<=1000000;i++){
        for(int k=1;k<pos[i].size();k++){
            sum+=(ll)(n-pos[i][k]+1)*(pos[i][k]-pos[i][k-1]);
        }
    }
    cout<<sum;
    return 0;
}

K - Kangaroo Puzzle

题意：在一个20×20的地图上，11表示有袋鼠，00表示有障碍物，边界外和障碍物上不能走。
要求给出一个50000步以内的操作，每一步操作为'L', 'R', 'U', 'D', 表示所有袋鼠一起动的方向，如果某个袋鼠下一个地方是不能走的，那么它那一步会忽略，使得所有袋鼠都聚集在一起。

思路：因为20x20非常小且有50000步可以操作，因此随机输出50000个  'L', 'R', 'U', 'D', 即可。（神奇）

代码：

char a[25][25];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    getchar();
    for(int i=1;i<=n;i++){
        scanf("%s",a);
    }
    n=50000;
    char s[5]="URLD";
    while(n--){
        printf("%c",s[rand()%4]);
    }
    return 0;
}