2020杭电多校联合训练(第十场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第十场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.Anti-hash Test

题意

题解

代码


B.Network Test

题意

题解

代码


C.Mine Sweeper

题意

题解

代码


D.Permutation Counting

题意

题解

代码


E.Tree Cutting

题意

题解

代码


F.Divide and Conquer

zyj (赛后)

题意

二维平面上给出$n$个点,保证$n$是4的倍数,要你给出两条直线将这$n$个点四等分。

题解

首先确定一条斜率接近0的直线$l_1$,用$l_1$将这$n$个点平分,这部分应该不难做到。
然后用二分斜率的方法去确定直线$l_2$了,具体做法如下:
不难得知二分的范围是$[0,pi]$,假设二分的斜率为$\theta$,那么$l_2$的一般形式为$y=\frac{sin(\theta)}{cos(\theta)} x + b$,于是可以将$n$个点用$l_2$分为两部分,此时只需考察$l_1$上方的点和$l_2$上方的点的交集与$n/4$的大小关系即可。
在得到边界斜率后,用$l_2$的边界点$id[n/2]$和$id[n/2+1]$去微调直线$l_2$,使得没有点在$l_2$上即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define mp make_pair
const int maxn=(int)1e5+10;
const double eps=1e-8;
const int inf=(int)9e8+7;
int n,x[maxn],y[maxn],id[maxn],ok[maxn],idd[maxn];
int ax[5],ay[5];
int check(double ag){
    double Cos=cos(ag),Sin=sin(ag);
    rep(i,1,n) idd[i]=i;
    sort(idd+1,idd+1+n,[&](int a,int b){
        return Cos*y[a]-Sin*x[a]>Cos*y[b]-Sin*x[b];
    });//y=Sin/Cos*x+b;
    int ans=0;
    rep(i,1,n/2) ans+=ok[idd[i]];
    return ans;
}
void solve(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d%d",&x[i],&y[i]),id[i]=i,ok[i]=0;
    sort(id+1,id+1+n,[&](int a,int b){
        return mp(y[a],x[a])<mp(y[b],x[b]);
    });rep(i,1,n/2) ok[id[i]]=1;
    ax[1]=-inf;ax[2]=inf+x[id[n/2]]+x[id[n/2+1]];
    ay[1]=y[id[n/2+1]];ay[2]=y[id[n/2]];
    if(y[id[n/2]]==y[id[n/2+1]]) ay[1]++,ay[2]--;
    double l=0,r=acos(-1.0);
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)>=n/4) r=mid;
        else l=mid;
    }check(r);
    int dx=x[idd[n/2+1]]-x[idd[n/2]],dy=y[idd[n/2+1]]-y[idd[n/2]];
    int c=inf/max(abs(dx),abs(dy));dx*=c;dy*=c;
    ax[3]=x[idd[n/2]]-dx+1;ay[3]=y[idd[n/2]]-dy;
    ax[4]=x[idd[n/2+1]]+dx-1;ay[4]=y[idd[n/2+1]]+dy;
    rep(i,1,4) printf(i&1?"%d %d ":"%d %d\n",ax[i],ay[i]);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

G.Coin Game

lmj 赛后

题意

$n$个位置,每个位置有$a_i,b_i,a_i$三个值,选完上一个值才能选下一个值,设$f(x)$为选$x$个值的最大值,求$f(1)^f(2)^……^f(m)$

题解

转化为背包问题,花费$1$的代价选择$a_i$,花费$2$的代价选择$a_i+b_i$,可以发现这一定是按照性价比选择,贪心选择,对于$f(x)$,其一定是$f(x-1)$的基础上选代价为$1$的物品或者是扔掉一个代价为$1$的物品选一个代价为$2$的物品,使用2个指针记录分别选到第几大即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
typedef unsigned long long ull;
const int N=5e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
constexpr int threshold=10000000;
ull k1,k2;
int a[N],b[N];
ull xorShift128Plus(){
    ull k3=k1,k4=k2;
    k1=k4;
    k3^=(k3<<23);
    k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
void gen(int n,ull _k1,ull _k2)
{
    k1=_k1,k2=_k2;
    for(int i=1;i<=n;i++){
        a[i]=xorShift128Plus()%threshold+1;
        b[i]=xorShift128Plus()%threshold+1;
    }
}
bool cmp(int x,int y)
{
    return x>y;
}
int c[N],d[N];
int pos[2];
void work()
{
    int n,m;
    while(~scanf("%d%d%llu%llu",&n,&m,&k1,&k2)){
        gen(n,k1,k2);
        for(int i=1;i<=n;i++){
            c[i]=a[i];
            d[i]=a[i]+b[i];
        }
        sort(c+1,c+n+1,cmp);
        sort(d+1,d+n+1,cmp);
        pos[0]=1;
        pos[1]=1;
        c[n+1]=0;
        d[n+1]=0;
        ll now=0;
        ll ans=0;
        for(int i=1;i<=m;i++){
            if(pos[0]==1){
                now+=c[pos[0]];
                pos[0]++;
            }else{
                if(d[pos[1]]-c[pos[0]-1]>c[pos[0]]){
                    now+=d[pos[1]]-c[pos[0]-1];
                    pos[0]--,pos[1]++;
                }else{
                    now+=c[pos[0]];
                    pos[0]++;
                }
            }
            ans^=now;
        }
        printf("%lld\n",ans);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

H.I do not know Graph Theory!

题意

题解

代码


I.Photography

题意

题解

代码


J.Tic-Tac-Toe-Nim

lmj 2:18:06 +0

题意

给定一个九宫格,当某行或者某列全为0时赢,两个人轮流进行操作,可以选择一堆减去任意数。两人的第一次操作一定为将某一堆变成0,求第一步有多少种操作能使得第一个人赢

题解

考虑最后情况 一定是3个互不同行同列的0,剩下6个位置均为1。枚举第三个0的位置,可以得到另外2个0的两种选择方案,那么能否获胜就是第三个0位置的值异或上(剩下6个位置的值-1)。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[4][4];
int ans[4][4];
void work()
{
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            scanf("%d",&a[i][j]);
            ans[i][j]=1;
        }
    }
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            int x1=i%3+1;
            int y1=j%3+1;
            int x2=x1%3+1;
            int y2=y1%3+1;
            int cnt=0;
            for(int k=1;k<=3;k++){
                for(int t=1;t<=3;t++){
                    if(k==i&&t==j||k==x1&&t==y1||k==x2&&t==y2){
                        if(k==i&&t==j){
                            cnt^=a[i][j];
                        }
                        continue;
                    }
                    cnt^=(a[k][t]-1);
                }
            }
            // printf("%d %d %d %d %d\n",x1,y1,x2,y2,cnt);
            if(cnt==0){
                ans[x1][y1]=0;
                ans[x2][y2]=0;
            }
            x1=i%3+1;
            y1=(j-1)%3;
            if(y1==0)y1=3;
            x2=x1%3+1;
            y2=(y1-1)%3;
            if(y2==0)y2=3;
            cnt=0;
            for(int k=1;k<=3;k++){
                for(int t=1;t<=3;t++){
                    if(k==i&&t==j||k==x1&&t==y1||k==x2&&t==y2){
                        if(k==i&&t==j){
                            cnt^=a[i][j];
                        }
                        continue;
                    }
                    cnt^=(a[k][t]-1);
                }
            }
            if(cnt==0){
                ans[x1][y1]=0;
                ans[x2][y2]=0;
            }
        }
    }
    int sum=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            sum+=ans[i][j];
        }
    }
    printf("%d\n",sum);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

K.Task Scheduler

题意

题解

代码

Responses