2018 ACM-ICPC 南京站

A Adrien and Austin

这是https://vjudge.net/contest/255624#status//M/0/ 的简化

 if(K == 1)
    printf("%s\n",(N&1)?"Adrien":"Austin");
   else 
    printf("%s\n",(N!= 0)?"Adrien":"Austin");

D. Country Meow

三分算法枚举圆心的位置


const int maxn = 100+10;
struct Point{
  double x,y,z;
};
Point p[maxn];
double a[maxn];
int n;
inline double mysqr(double x){
  return x*x;
}
double cal(){
  double ans = 0;
  for(int i = 1;i <= n; ++i)
  {
    ans = max(ans,sqrt(mysqr(p[i].x-a[0])+mysqr(p[i].y-a[1])+mysqr(p[i].z-a[2])));
  }
  return ans;
}

double check(int cnt ){
  if(cnt >= 3) return cal();
  double l = -100000,r = 100000;
  double ans = 1e10;
  for(int i = 0;i < 50; ++i){
    double mid1 = (2*l+r)/3;
    double mid2 = (l+2*r)/3;
    a[cnt] = mid1;
    double ans1 = check(cnt+1);
    a[cnt] = mid2;
    double ans2 = check(cnt+1);

    if(ans1 < ans2)
       r = mid2,ans = min(ans,ans1);
     else
       l = mid1,ans = min(ans,ans2);
  }
  return ans;
}
int main(void)
{
    
    cin>>n;
    for(int i =1;i<= n; ++i)
      scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
    printf("%.10f\n",check(0));

   return 0;
}

Problem G. Pyramid

C(n+3,4) 不要问我为什么心痛推不出来

Problem I. Magic Potion

最大流
首先建源点s和汇点t
s - > s1 容量为n
s -> s2 容量为k
然后再从s1和s2 连到n个点，之后把该加的边加上

const double eps = 1e-6;
const LL     mod = 1e9 + 7;
const int LEN = 20000+1000;
const int maxn = 1e8;
struct Edge{
  int from,to,cap,flow;
  Edge(int u,int v,int w,int f): from(u),to(v),cap(w),flow(f){}
};
struct Dinic{
   int n,m,s,t;
   vector<Edge> edges;
   vector<int> G[LEN];
   int a[LEN];
   int vis[LEN];
   int d[LEN];
   int cur[LEN];//好吧就是点, 代表该点在一次求增广的过程中搜索到了那条边,意思就是从这条边往下肯定搜索不到结果了
   void init(int n)
   {
       this->n  = n;
       for(int i = 0;i < n; ++i)
        G[i].clear();
       edges.clear();
   }
   void Add(int u,int v,int w)
   {
       edges.push_back(Edge(u,v,w,0));
       edges.push_back(Edge(v,u,0,0));
       m = edges.size();
       G[u].push_back(m-2);
       G[v].push_back(m-1);
   }
   bool Bfs(void)//分层
   {
      me(d);
      me(vis);
      d[s] = 0;
      vis[s] = 1;

      queue<int> Q;
      Q.push(s);
      while(!Q.empty())
      {
          int q = Q.front();Q.pop();

          for(size_t i = 0;i < G[q].size();++i)
          {
              Edge &tmp = edges[G[q][i]];
              if(!vis[tmp.to]&&tmp.cap>tmp.flow)
              {
                  vis[tmp.to] = 1;
                  d[tmp.to] = d[q] + 1;
                  Q.push(tmp.to);
              }
          }
      }
      return vis[t];
   }
   int Dfs(int node,int a)
   {

       if(node == t||a == 0)
        return a;
       int flow =  0,f;
       for(int &i = cur[node];i < (int)G[node].size();++i)
       {
          Edge &tmp = edges[G[node][i]];
          if(d[tmp.to]==d[node]+1&&(f=Dfs(tmp.to,min(a,tmp.cap-tmp.flow)))>0)
          {
              flow += f;
              tmp.flow += f;
              edges[G[node][i]^1].flow -= f;
              a -= f;
              if(a==0)
                break;
          }
       }
       return flow;
   }
   int MaxFlow(int s,int t)
   {
       this->s = s;
       this->t = t;
       int flow = 0;
       while(Bfs())
       {
           me(cur);
           flow += Dfs(s,maxn);
       }
       return flow;

   }
};
Dinic dinic;
int main()
{
    int N,M,K;
    scanf("%d%d%d",&N,&M,&K);
    int d1 = N+M+1;
    int d2 = N+M+2;
    int dest = N+M+3;
    int d3 = N+M+4;
        dinic.init(N+M+10);
        for(int i = 1;i <= N; ++i)
        {
          int t;
          scanf("%d",&t);
          for(int j = 1;j <= t; ++j){
            int v;
            scanf("%d",&v);
            dinic.Add(i,v+N,1);
          }
        }
        for(int i  = 1;i <= N; ++i)
          dinic.Add(d1,i,1),dinic.Add(d2,i,1);
        dinic.Add(d3,d1,N);
        dinic.Add(d3,d2,K);
        for(int i = 1;i <= M; ++i)
          dinic.Add(N+i,dest,1);

        int  ans = dinic.MaxFlow(d3,dest);
        printf("%d\n",ans);




    return 0;
}

Problem J. Prime Game

记录下这个素数出现的位置就行了

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
#define Pb push_back
const int maxn = 1e6+100;
int a[maxn];
bool check[maxn];
int Prime[maxn];
vector<int> vec[maxn];
int tot = 1;
std::vector<int> v;
void Euler_shai(void){
    int n = 1e3+1;
    memset(check,0,sizeof(check));
    for(int i = 2;i <= n; ++i){
        if(!check[i]){
            Prime[tot++] = i;
        }
            for(int j = 1;j < tot; ++j){
                if(i*Prime[j] > n) break;
                    check[i*Prime[j]]  =1 ;
                if(i % Prime[j]==0) break;
            }
    }
} 
int main(void){
    Euler_shai();
    map<int,int> ma;
    int n;
    cin>>n;
    for(int i = 1;i <= n; ++i){
        scanf("%d",&a[i]);
    }
    // cout<<"DEBUG"<<endl;
    for(int i = 1;i <= n; ++i){
        // cout<<"DEBUG"<<endl;
       for(int j = 1;Prime[j]*Prime[j] <= a[i] &&j < tot; ++j){
        if(a[i] %  Prime[j] == 0){
            vec[Prime[j]].Pb(i);
            while(a[i] % Prime[j] == 0) a[i] /= Prime[j];
        }
       
       }
        if(a[i] != 1)
            vec[a[i]].Pb(i);
    }
    LL ans = 0;
    for(int i = 1;i < maxn; ++i){
        if(vec[i].empty()) continue;
        int l = 0;
        for(int j = 0;j < (int) vec[i].size(); ++j)
        {
            ans += 1ll*(vec[i][j]-l)*(n+1-vec[i][j]);
            l = vec[i][j];
        }
    }
    cout<<ans<<endl;





    return 0;
}

Problem K. Kangaroo Puzzle

int main(void)
{
    int n;
    srand(time(0));
    n = 50000;
    string s;
    char a[5]= "UDRL";
    while(n--) s += a[rand()%4];
    cout<<s<<endl; 

   return 0;
}