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;
}

NWERC2020

Contest link

Experience

Problem A. Atomic Energy

Description

Solution

Analysis

Attention

Code

Problem D. Dragon Balls

Description

Solution

Analysis

Attention

Code

Problem E. Endgame

Description

Solution

Analysis

Attention

Code

Problem J. Joint Excavation

Description

Solution

Analysis

Attention

Code

国庆随笔

gym102114A

Enderturtle

	#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;
	}

Contest link

Experience

Problem A. Atomic Energy

Description

Solution

Analysis

Attention

Code

Problem D. Dragon Balls

Description

Solution

Analysis

Attention

Code

Problem E. Endgame

Description

Solution

Analysis

Attention

Code

Problem J. Joint Excavation

Description

Solution

Analysis

Attention

Code

微信扫一扫：分享

国庆随笔

gym102114A

Enderturtle