本文共 14633 字，大约阅读时间需要 48 分钟。

A Relic Discovery

温暖的签到题。

#include
   
    using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    while(T --)    {        int ans = 0 ;        int n ;        cin >> n ;        int x , y ;        for(int i = 1 ; i <= n ; i ++)  cin >> x >> y , ans += x * y ;        cout << ans << '\n' ;    }    return 0 ;}
   

B Pocket Cube

上层顺时针等价于下层逆时针。因此只有种情况。

#include
   
    using namespace std;bool ok(int a,int b,int c,int d){	if(a==b&&b==c&&c==d)return 1;	return 0;	}void solve(){	int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x;	cin>>a>>b>>c>>d;	cin>>e>>f>>g>>h;	cin>>i>>j>>k>>l;	cin>>m>>n>>o>>p;	cin>>q>>r>>s>>t;	cin>>u>>v>>w>>x;	if(ok(a,b,c,d)&&ok(e,f,g,h)&&ok(i,j,k,l)&&ok(m,n,o,p)&&ok(q,r,s,t)&&ok(u,v,w,x))puts("YES");	else if(ok(a,b,c,d)&&ok(i,j,k,l)&&ok(q,s,e,f)&&ok(g,h,u,w)&&ok(v,x,o,p)&&ok(m,n,r,t))puts("YES");	else if(ok(a,b,c,d)&&ok(i,j,k,l)&&ok(q,s,o,p)&&ok(g,h,r,t)&&ok(v,x,e,f)&&ok(m,n,u,w))puts("YES");	else if(ok(e,f,g,h)&&ok(m,n,o,p)&&ok(a,b,w,x)&&ok(u,v,i,j)&&ok(k,l,s,t)&&ok(q,r,c,d))puts("YES");	else if(ok(e,f,g,h)&&ok(m,n,o,p)&&ok(a,b,s,t)&&ok(u,v,c,d)&&ok(k,l,w,x)&&ok(q,r,i,j))puts("YES");	else if(ok(q,r,s,t)&&ok(u,w,w,x)&&ok(a,c,n,p)&&ok(e,g,b,d)&&ok(i,k,f,h)&&ok(m,o,j,l))puts("YES");	else if(ok(q,r,s,t)&&ok(u,w,w,x)&&ok(a,c,f,h)&&ok(e,g,j,l)&&ok(i,k,n,p)&&ok(m,o,b,d))puts("YES");	else puts("NO");}int main(){	int T;	scanf("%d",&T);	while(T--)solve();	return 0;}
   

C Pocky

猜公式。

#include 
   
    using namespace std;using db = double;void solve(){    db d, l;    scanf("%lf%lf", &l, &d);    if(l<=d) printf("0.000000\n");    else printf("%.6f\n", 1.0+log(l/d));}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}
   

D Lucky Coins

留坑。

E Fibonacci

留坑。

F Lambda Calculus

英语写的实在过于上等，我生生读了两个小时才明白啥意思。

其实就是一个嵌套的函数。定义中不是自由元，中是自由元。

个人理解可以认为是自由元集合。

两个没有嵌套关系的变量没有关系，就是在第一个中不是自由元的变量，第二个中是自由元的变量，那这个变量可以作为自由元。

直接递归做就行了。注释中举了例子帮助理解。

#include
   
    using namespace std ;const int maxn = 1e7 + 10 ;const string lambda = "lambda" ;char s[maxn] ;int n , br[maxn] ;set
    
      ans ;vector
     
       a ;bool is_char(char c){    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '-' ;}void tokenize(){    a.clear() ;    for(int i = 0 ; i < n ; i ++)    {        if(s[i] == '(')  a.push_back("(") ;        else if(s[i] == ')')  a.push_back(")") ;        else if(is_char(s[i]))        {            string t = "" ;            t += s[i] ;            while(i + 1 < n && is_char(s[i + 1]))  t += s[i + 1] , i ++ ;            a.push_back(t) ;        }    }}//这个东西是左结合的//(lambda(x)(lambda(y) (x y)))  没有自由元//((lambda(x) x) x)  自由元是xvoid solve(set
      
       lim , int l , int r){    if(a[l] == "(")    {        if(a[l + 1] == lambda)        {            lim.insert(a[l + 3]) ; //存在于lambda里面的元素不是自由元            solve(lim , l + 5 , r) ;        }        else        {            if(a[l + 1] == "(") //划分括号            {                int mid = br[l + 1] + 1 ;                solve(lim , l + 1 , mid - 1) ;                solve(lim , mid , r) ;            }            else            {                solve(lim , l + 1 , l + 1) ; //这就是(lambda(x) t)的t                solve(lim , l + 2 , r) ;            }        }    }    else    {        if(!lim.count(a[l]))  ans.insert(a[l]) ;    }}int main(){    static int T ;    scanf("%d" , &T) ;    fgets(s , maxn , stdin) ;    for(int cas = 1 ; cas <= T ; cas ++)    {        ans.clear() ;        fgets(s , maxn , stdin) ;        n = strlen(s) ;        tokenize() ;        n = a.size() ;        stack
       
         st ;        for(int i = 0 ; i < n ; i ++)        {            if(a[i] == "(")  st.push(i) ;            else if(a[i] == ")")  br[st.top()] = i , st.pop() ;        }        set
        
          lim ; solve(lim , 0 , n - 1) ; if(ans.empty()) printf("Case #%d: \n" , cas) ; else { printf("Case #%d:" , cas) ; for(auto s : ans) printf(" %s" , s.c_str()) ; puts("") ; } } return 0 ;}
        
       
      
     
    
   

G Coding Contest

把概率取对数就转成最小费用最大流了，最后对答案取即可。

#include 
   
    using namespace std;using db = double;const db eps = 1e-8;inline db sgn(db x) { return (x<-eps ? -1 : x>eps); }namespace MCMF{    const int N = 1005, M = 1e5 + 5, inf = 1e9;    const db dinf = 1e18;    int cnt, head[N];    struct edge    {        int next, to, w;        db f;     }e[M<<1];    inline void addedge(int u, int v, int w, db f)    {        e[++cnt] = {head[u], v, w, f};        head[u] = cnt;    }    int n, s, t;    int flow;    db cost;    bool inq[N];    int p[N], a[N];    db d[N];    void init(int _n, int _s, int _t)    {        n = _n, s = _s, t = _t;        cnt = 1, flow = 0, cost = 0.0;        memset(head, 0, (n+1)<<2);    }    void add(int u, int v, int cap, db cost)    {        addedge(u, v, cap, cost), addedge(v, u, 0, -cost);    }    bool spfa()    {        for(int i=1; i<=n; i++) d[i] = dinf, inq[i] = 0;        queue
    
      q;        q.push(s);        d[s] = 0.0, a[s] = inf;        while(!q.empty())        {            int u = q.front(); q.pop();            inq[u] = 0;            for(int i=head[u]; i; i=e[i].next)            {                int v = e[i].to;                if(e[i].w&&sgn(d[v]-d[u]-e[i].f)>0)                {                    d[v] = d[u] + e[i].f;                    p[v] = i;                    a[v] = min(a[u], e[i].w);                    if(!inq[v])                     {                        inq[v] = 1;                        q.push(v);                    }                }            }        }        return sgn(d[t]-dinf)!=0;    }    void go()    {        while(spfa())        {            flow += a[t], cost += a[t]*d[t];            int u = t;            while(u!=s)            {                e[p[u]].w -= a[t], e[p[u]^1].w += a[t];                u = e[p[u]^1].to;            }        }    }}int n, m;void solve(){    scanf("%d%d", &n, &m);    MCMF::init(n+2, n+1, n+2);    for(int i=1; i<=n; i++)    {        int a, b; scanf("%d%d", &a, &b);        MCMF::add(MCMF::s, i, a, 0);        MCMF::add(i, MCMF::t, b, 0);    }    for(int i=1; i<=m; i++)    {        int u, v, w;        db f;        scanf("%d%d%d%lf", &u, &v, &w, &f);        f = 1 - f;        if(!w) continue;        MCMF::add(u, v, 1, 0);        MCMF::add(u, v, w-1, -log(f));     }    MCMF::go();    printf("%.2f\n", 1-exp(-MCMF::cost));}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}/*14 42 00 33 00 31 2 5 0.53 2 5 0.51 4 5 0.53 4 5 0.5*/
    
   

H Pattern

留坑。

I Travel Brochure

。其中表示叉积。容易发现右边式子是一个有向面积。因此求一个凸包即可。

#include
   
    #define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << #x << " = " << x << '\n'#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;typedef long long ll ;typedef long double ld ;typedef pair
    
      pii ;typedef pair
     
       pll ;typedef double db ;const int mod = 998244353 ;const int maxn = 2e5 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; int n ;struct point{    double x , y ;    bool operator < (const point &s) const    {        if(x != s.x)  return x < s.x ;        else  return y < s.y ;    }} p[maxn] ;double cross(point p0 , point p1 , point p2) {    double x1 , y1 , x2 , y2 ;    x1 = p1.x - p0.x , y1 = p1.y - p0.y ;    x2 = p2.x - p0.x , y2 = p2.y - p0.y ;    return x1 * y2 - x2 * y1 ; }double area(int n){    }struct Convex_hull{    int cnt , sta[maxn] ;    void init()    {        cnt = 0 ;    }    double sq(double x)    {        return x * x ;    }    double d(point p1 , point p2)    {        return sqrt(sq(p1.x - p2.x) + sq(p1.y - p2.y)) ;    }    void solve()  //注意左下角的点存储了两次 分别是数组中的第一个点和最后一个点     {        sort(p + 1 , p + n + 1) ;        sta[++ cnt] = 1 ;        for(int i = 2 ; i <= n ; i ++)         {            //假如想让凸包的边上有多个点，那就把 <= 改成 <             while(cnt >= 2  && cross(p[sta[cnt - 1]] , p[sta[cnt]] , p[i]) <= 0)            cnt -- ;            sta[++ cnt] = i ;        }        int temp = cnt ;        for(int i = n - 1 ; i >= 1 ; i --)        {            while(cnt > temp && cross(p[sta[cnt - 1]] , p[sta[cnt]] , p[i]) <= 0)            cnt -- ;            sta[++ cnt] = i ;        }        //double ans = 0 ;        //for(int i = 1 ; i <= cnt - 1 ; i ++)  ans += d(p[sta[i]] , p[sta[i + 1]]) ;         double sum = 0 ;        rep(i , 1 , cnt - 1)  sum += cross((point){0.0 , 0.0} , p[sta[i]] , p[sta[i + 1]]) ;        //sum += cross((point){0.0 , 0.0} , p[n] , p[1]) ;        cout << fixed << setprecision(5) << fabs(sum / 2) << '\n' ;    }} convex_hull ; int main(){    ios ;    int T ;    cin >> T ;    while(T --)    {        cin >> n ;        double a , b = 0 ;        for(int i = 1 ; i <= n ; i ++)        {            cin >> a ;            b += a ;            p[i].x = b / a ;            p[i].y = b ;        }        convex_hull.init() ;        convex_hull.solve() ;    }    return 0 ;}
     
    
   

J Cliques

对于任意三个点组成的三元组，容易发现如果所有连通块都是完全图，那么之间有条边。因此之间有条边的三元组是不合法的，要想把这个三元组变为合法的三元组，需要删边或者加边，总共种情况，修改一条边的状态至多影响个三元组，暴搜复杂度。

#include
   
    using namespace std;#define M 105int G[M][M];struct node{	int x,y,z;	bool operator <(const node &A)const{		if(x!=A.x)return x
    
     b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						Q[++num]=(node){a,b,c};						tttt++;						mark[a][b][c]=1;					}					else if(cnt==3){						tttt--;						mark[a][b][c]=0;					}				}			}			dfs(x+1);			G[p.x][p.y]=G[p.y][p.x]=0;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.y){					int cnt=1;					if(G[i][p.x])cnt++;					if(G[i][p.y])cnt++;					int a=i,b=p.x,c=p.y;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						num--;						tttt--;						mark[a][b][c]=0;					}					else if(cnt==3){						tttt++;						mark[a][b][c]=1;					}				}			}		}		else {			G[p.x][p.y]=G[p.y][p.x]=0;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.y){					int cnt=0;					if(G[i][p.x])cnt++;					if(G[i][p.y])cnt++;					int a=i,b=p.x,c=p.y;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						Q[++num]=(node){a,b,c};						tttt++;						mark[a][b][c]=1;					}					else if(cnt==1){						tttt--;						mark[a][b][c]=0;					}				}			}			dfs(x+1); 			G[p.x][p.y]=G[p.y][p.x]=1;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.y){					int cnt=0;					if(G[i][p.x])cnt++;					if(G[i][p.y])cnt++;					int a=i,b=p.x,c=p.y;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						num--;						tttt--;						mark[a][b][c]=0;					}					else if(cnt==1){						tttt++;						mark[a][b][c]=1;					}				}			}		}		ok[p.x][p.y]=0;	}	if(!ok[p.x][p.z]){		ok[p.x][p.z]=1;		if(!G[p.x][p.z]){			G[p.x][p.z]=G[p.z][p.x]=1;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.z){					int cnt=1;					if(G[i][p.x])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.x,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						Q[++num]=(node){a,b,c};						tttt++;						mark[a][b][c]=1;					}					else if(cnt==3){						tttt--;						mark[a][b][c]=0;					}				}			}			dfs(x+1); 			G[p.x][p.z]=G[p.z][p.x]=0;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.z){					int cnt=1;					if(G[i][p.x])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.x,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						num--;						tttt--;						mark[a][b][c]=0;					}					else if(cnt==3){						tttt++;						mark[a][b][c]=1;					}				}			}		}		else {			G[p.x][p.z]=G[p.z][p.x]=0;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.z){					int cnt=0;					if(G[i][p.x])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.x,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						Q[++num]=(node){a,b,c};						tttt++;						mark[a][b][c]=1;					}					else if(cnt==1){						tttt--;						mark[a][b][c]=0;					}				}			}			dfs(x+1); 			G[p.x][p.z]=G[p.z][p.x]=1;			for(int i=1;i<=n;i++){				if(i!=p.x&&i!=p.z){					int cnt=0;					if(G[i][p.x])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.x,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						num--;						tttt--;						mark[a][b][c]=0;					}					else if(cnt==1){						tttt++;						mark[a][b][c]=1;					}				}			}		}		ok[p.x][p.z]=0;	}	if(!ok[p.y][p.z]){		ok[p.y][p.z]=1;		if(!G[p.y][p.z]){			G[p.y][p.z]=G[p.z][p.y]=1;			for(int i=1;i<=n;i++){				if(i!=p.y&&i!=p.z){					int cnt=1;					if(G[i][p.y])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.y,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						Q[++num]=(node){a,b,c};						tttt++;						mark[a][b][c]=1;					}					else if(cnt==3){						tttt--;						mark[a][b][c]=0;					}				}			}			dfs(x+1); 			G[p.y][p.z]=G[p.z][p.y]=0;			for(int i=1;i<=n;i++){				if(i!=p.y&&i!=p.z){					int cnt=1;					if(G[i][p.y])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.y,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						num--;						tttt--;						mark[a][b][c]=0;					}					else if(cnt==3){						tttt++;						mark[a][b][c]=1;					}				}			}		}		else {			G[p.y][p.z]=G[p.z][p.y]=0;			for(int i=1;i<=n;i++){				if(i!=p.y&&i!=p.z){					int cnt=0;					if(G[i][p.y])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.y,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						Q[++num]=(node){a,b,c};						tttt++;						mark[a][b][c]=1;					}					else if(cnt==1){						tttt--;						mark[a][b][c]=0;					}				}			}			dfs(x+1); 			G[p.y][p.z]=G[p.z][p.y]=1;			for(int i=1;i<=n;i++){				if(i!=p.y&&i!=p.z){					int cnt=0;					if(G[i][p.y])cnt++;					if(G[i][p.z])cnt++;					int a=i,b=p.y,c=p.z;					if(a>b)swap(a,b);					if(b>c)swap(b,c);					if(cnt==2){						num--;						tttt--;						mark[a][b][c]=0;					}					else if(cnt==1){						tttt++;						mark[a][b][c]=1;					}				}			}		}		ok[p.y][p.z]=0;	}}int kase;void solve(){	ans=11;num=0;tttt=0;	scanf("%d",&n);	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)scanf("%d",&G[i][j]);	memset(mark,0,sizeof(mark));	memset(ok,0,sizeof(ok));	for(int i=1;i<=n;i++)		for(int j=i+1;j<=n;j++)			for(int k=j+1;k<=n;k++){				int cnt=0;				if(G[i][j])cnt++;				if(G[i][k])cnt++;				if(G[j][k])cnt++;				if(cnt==2){					Q[++num]=(node){i,j,k};					tttt++;					mark[i][j][k]=1;				}			}	if(num>10*n){		printf("Case #%d: -1\n",++kase);		return;	}	dfs(0);	if(ans==11)printf("Case #%d: -1\n",++kase);	else printf("Case #%d: %d\n",++kase,ans);}int main(){	int T;	scanf("%d",&T);	while(T--)solve();	return 0;}
    
   

K Finding Hotels

留坑。

L Tower Attack

留坑。

M Generator and Monitor

留坑。