Contest link

link -> gym 103049

Experience

注意精度 Problem F

Problem A. Atomic Energy

Description

完全背包，物品的体积是$1,2…n$ 价值是$a_1,a_2…a_n$

给出$q$次询问，每次询问体积恰为$k$的背包的价值是多少

$1 \leq n \leq 100,q \leq 10^5\ 1 \leq a_i \leq 10^9,1 \leq k \leq 10^9$

Solution

Analysis

经典题，考虑大数据贪心，小数据DP。

小数据进行完全背包DP，大数据按照密度（$\frac{a_k}{k}$）贪心。

Attention

进行简单时间计算，DP的上限可以设为$10^5$。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    #define gc getchar
    il int read(){
        int x=0;bool f=1;char ch=gc();
        if(ch=='-') f=0;
        while(!isdigit(ch)) ch=gc();
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
        return f?x:-x;
    }
}
using io::read;
using namespace std;
/*---- head -----*/

#define N 100005
int n, q;
ll a[N], f[N];
int main(){
    n = read(); q = read();
    fo (i, 1, n) a[i] = read();
    fo (i, 1, n) f[i] = a[i];
    int up = 100000;
    fo (i, n + 1, up)
    {
        f[i] = a[1] + f[i - 1];
        fo (j, 1, n)
            f[i] = std::min(f[i], a[j] + f[i - j]);
    }
    fo (i, 1, q)
    {
        int now = read();
        if (now <= up)
            printf("%lld\n", f[now]);
        else
        {
            ll ans;
            fo (k, 1, n)
            {
                int x = (now - up) / k;
                if ((now - up) % k) ++x;
                ll s = x * a[k] + f[now - x * k];
                if (k == 1)
                    ans = s;
                else
                    ans = std::min(ans, s);
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

Problem D. Dragon Balls

Description

在2维平面的第一象限上（包括坐标轴）有$n$个点

你可以询问至多$1000$次，每次询问给出坐标$(x,y)$,每次会返回离该点的最近的点的距离的平方

点的范围$0 \leq x \leq 10^6,0\leq y \leq 10^6$

点的个数$1 \leq n\leq 7$

返回的距离$0 \leq d \leq2\times 10^{12}$

Solution

Analysis

官方题解给出了众多解法，这边提出一个简易交互做法。

第一次询问$(0,0)$

得到返回的值$d$，考虑枚举以$(0,0)$为圆心，半径为$\sqrt d$的圆上的整点。

注意到$d \leq 10^{12}$，在这个情景下，整点数目不会很多。

Attention

询问的点对$(x,y)$务必保证在数据范围内，否则评测姬会返回TLE。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    #define gc getchar
    il ll read(){
        ll x=0;bool f=1;char ch=gc();
        if(ch=='-') f=0;
        while(!isdigit(ch)) ch=gc();
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
        return f?x:-x;
    }
}
using io::read;
using namespace std;
/*---- head -----*/
int n;
int main(){
    n=read();
    ll mn=1e6;
    rep(id,1,n){
        puts("0 0");
        fflush(stdout);
        ll d=read();
        if(d==0) continue;
        for(register ll x=0;x*x<=d;++x){
            ll y=(ll)(sqrt(d-x*x)+0.1);
            if((y*y+x*x)!=d) continue;
            if(x>mn || y>mn) continue;
            printf("%lld %lld\n",x,y);
            fflush(stdout);
            ll d2=read();
            if(d2==0) break;
        }        
    }
    return 0;
}

Problem E. Endgame

Description

在$n \times n$的棋盘上两人进行移动。每次两人可以选择如下操作之一：

1.进行两次给定的移动 2.移动到任意没有棋子的位置 3.不移动

共有$n$个给定移动模式，负数表示向左或者向上，不能移动到界外

初始状态Alice在$a_x,b_x$，Bob在$b_x,b_y$，Alice先动，如果Alice能抓到Bob，则Alice获胜；

如果Alice能走到一个Bob不能走到的点，则平局在这个点；

其他情况，Bob获胜。

$2 \leq n \leq 10^5$

Solution

Analysis

对于Alice获胜，直接判断是否能走到

对于平局，考虑平局的点会很多（理由：移动模式的数量级在$n$，棋盘有$n \times n$个格点）

考虑随机化平局的点，如果能判断就平局；

其他情况Bob获胜。

Attention

待补严谨证明

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    #define gc getchar
    il int read(){
        int x=0;bool f=1;char ch=gc();
        if(ch=='-') f=0;
        while(!isdigit(ch)) ch=gc();
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
        return f?x:-x;
    }
}
using io::read;
using namespace std;
/*---- head -----*/
#define mp make_pair
map<pair<int,int> ,bool> table;
pair<int,int> a[100010];
int n,ax,ay,bx,by;

il bool ok(int dx,int dy,int x,int y){
    if(dx==0 && dy==0) return 1;
    if(table[mp(dx,dy)]) return 1;
    rep(i,1,n){
        int nx=x+a[i].first;
        int ny=y+a[i].second;
        if(nx<1 || ny<1 || nx>n || ny>n) continue;
        if(table[mp(dx-a[i].first,dy-a[i].second)]) return 1;
    }
    return 0;
}

int main(){
    n=read();
    ax=read(),ay=read(),bx=read(),by=read();
    rep(i,1,n){
        int dx=read(),dy=read();
        table[make_pair(dx,dy)]=1;
        a[i]=make_pair(dx,dy);
    }
    if(ok(bx-ax,by-ay,ax,ay)){ puts("Alice wins");return 0;}
    int T=500;
    while(T--){
        int x=rand()%n+1,y=rand()%n+1;
        if(!ok(x-bx,y-by,bx,by)){
            printf("tie %d %d",x,y);
            return 0;
        }
    }
    puts("Bob wins");
    return 0;
}

Problem J. Joint Excavation

Description

蛮有趣的一个题

给一个$n$个点$m$条边的无向连通图。

求构造一种方案。

删除图中的一条简单路径，使剩下的部分可以分成两个集合$S_1,S_2$，满足$|S_1| = |S_2|$，$S_1$与$S_2$不连通。

保证数据给出一组解。

$1\leq n \leq 210^5,0\leq m \le 210^5$

Solution

Analysis

考虑一个基本性质，无向图的dfs树是没有横叉边，只有返祖边的。如果删除dfs树从根开始的一条路径，那么各个子树一定不互相连通。

此时题目完全等价于：给定一棵树，从根节点删除一条路径，使剩余完整的子树可以分成数量相同的两部分。

考虑一种贪心策略：

对于一个点的轻儿子，我们将分配给$S_1$或者$S_2$（取决于当前谁的$|S|$更小）

对于一个点的重儿子，我们考虑两种情况，如果分配给集合已经满足题意，就直接return，如果没有我们可以继续这个操作。

Attention

事实上，我们可以通过以下方式来证明为什么这样子操作是对的。

对于一个子树，我们考虑当$|S_1| \le |S_2|$就加入到$S_1$中。

这样子每轮操作完，必定保证此时$|S_1| \ge |S_2|$，每一层都保证这个，并且二者的差会逐渐缩小

对于最后一层，一定有一个单独的叶子节点可以产生贡献（正/负），使得$|S_1|=|S_2|$。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    #define gc getchar
    il int read(){
        int x=0;bool f=1;char ch=gc();
        if(ch=='-') f=0;
        while(!isdigit(ch)) ch=gc();
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
        return f?x:-x;
    }
}
using io::read;
using namespace std;
/*---- head -----*/
const int N=200100,M=200100;
struct node{
    int sz,v;
    il bool operator <(const node & other) const{
        return sz>other.sz;
    }
};vector<node> g[N];
struct Edge{
    int v,nxt;
} e[M<<1];int head[N],tot;
bool vis[N];
il int dfs(int u){
//    cerr<<u<<endl;
    vis[u]=1;
    int sz=1;
    for(register int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(vis[v]) continue;
        int sz_v=dfs(v);
        sz+=sz_v;
        g[u].push_back((node){sz_v,v});
    }
    sort(g[u].begin(),g[u].end());
    return sz;
}
int suma,sumb,ans,res[N],a[N],b[N],cnt_a,cnt_b;

il void solve(int u){
    res[++ans]=u;
    for(register unsigned i=1;i<g[u].size();++i){
        int v=g[u][i].v,sz=g[u][i].sz;
        if(suma<=sumb){
            suma+=sz;
            a[++cnt_a]=v;
        }
        else{
            sumb+=sz;
            b[++cnt_b]=v;
        }
    }
    if(g[u].size()){
        int v=g[u][0].v,sz=g[u][0].sz;
        if(suma+sz==sumb){
            suma+=sz;
            a[++cnt_a]=v;
            return;
        }
        if(sumb+sz==suma){
            sumb+=sz;
            b[++cnt_b]=v;
            return;
        }
        solve(v);
    }
}
int n,m;
il void add_edge(int u,int v){
    e[++tot]=(Edge){v,head[u]};
    head[u]=tot;
}
il void print(int u){
    printf("%d ",u);
    for(register unsigned i=0;i<g[u].size();++i){
        int v=g[u][i].v;
        print(v);
    }
}
int main(){
    n=read();m=read();
    rep(i,1,m){
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1);
    solve(1);
    printf("%d %d\n",ans,suma);
    rep(i,1,ans) printf("%d ",res[i]);
    puts("");
    rep(i,1,cnt_a) print(a[i]);
    puts("");
    rep(i,1,cnt_b) print(b[i]);
    puts("");
    return 0;
}