xcpc区域赛训练记录


有训练记录在之前的寒假复健随笔里

因为寒假过了所以开了个新随笔。

ICPC2020济南

C stone game

全部转成在模$3$意义下

发现把$1$和$2$尽量转化成3是最优的

然后就先让$1$和$2$配对,剩下单独的$1$和$2$再自己想办法凑成$3$

#include 
using namespace std;
long long a,b,c,ans;
int main(){
    scanf("%lld%lld%lld",&a,&b,&c);
    if (a>=b){
        long long y=a-b;
        ans=ans+2ll*b;
        ans=ans+(y/3)*3;
        long long t=y%3;
        if (t==2) ans++;
    }
    else{
        long long y=b-a;
        ans=ans+2ll*a;
        ans=ans+(y/3)*6ll;
        long long t=y%3;
        if (t==2) ans=ans+4ll;
    }
    cout<<ans;
    return 0;
}

D.Fight against involution

合理内卷(

最native的想法肯定是全取$l_i$,但是显然不行,因为可能会导致排名发生变化

于是我们按照$r_i$先排序,这样得到的就是最高排名

然后对于每个位置,它至少要取到前面的$l_i$中的$max$来保证自己的排名,因为所有人都是最轻松的选择

直接模拟即可。

#include 
using namespace std;
int N;
long long ans;
struct Node{
    long long l,r;
}a[100005];
int temp(Node a,Node b){
    return (a.rb.l));
}
int main(){
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
     scanf("%lld%lld",&a[i].l,&a[i].r);
    sort(a+1,a+N+1,temp);
    long long nw=0;
    for (int i=1;i<=N;i++){
        if (a[i].l>nw) nw=a[i].l;
        ans+=nw;
    }
    cout<<ans;
    return 0;
}

L.Bit Sequence

如果没有$+m$的限制是个显然的数位$dp$

但是有$+m$

有点像之前$dls$讲的一个题

低位不影响高位

所以我们先把前$128$个数字暴力拿出来,$+m$,然后把这个数字拆成左右半边考虑,左边数位$dp$统一统计一下即可。

代码是学长写的

#include
#define ll long long
using namespace std;
ll dp[64][2][128][2][2];
int v[65],a[105];
int m;
ll cal(int st,int s,int t)
{
    int f=1;
    for(int i=0;i)
    {
        if(st+i<128) f&=(__builtin_parity(st+i)^s)==a[i];
        else f&=(__builtin_parity(st+i)^s^t)==a[i];
    }
    return f;
}
ll dfs(int pos,int limit,int st,int s,int t)
{
    if(pos==-1) return cal(st,s,t) ;
    ll &res=dp[pos][limit][st][s][t];
    if(res!=-1) return res;
    res=0;
    int up=limit?v[pos]:1;
    for(int i=0;i<=up;i++)
    if(pos>6) res+=dfs(pos-1,limit&i==up,(st*2+i)&127,s^i,i&(!t));
    else res+=dfs(pos-1,limit&i==up,(st*2+i)&127,s,t);
    //cout<
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        ll L;
        cin>>m>>L;
        for(int i=0;i>a[i];
        memset(dp,-1,sizeof dp);
        int len=0;
        for(;L;L>>=1)v[len++]=L&1;

        cout<1,1,0,0,0)<<'\n';
    }

}

 赛后补题:

A.atrix Equation

草了,我高消的板子有问题

发现操作2可以转化成$xor$,操作1可以转化成$or$

于是我们可以有一个暴力的想法,解$n^2$个异或方程组

然后仔细思考,不难发现同一列每$n$个方程组是一组的,不涉及其他列的变量

于是就变成解$n$次,一次$n$个方程组

这东西可以直接$n^4/64$,$bitset$优化一下即可。

高消板子有问题调了大半场没出,麻了

#include 
using namespace std;
const long long fish=998244353;
bitset<205> a[205];
int aa[205][205],b[205][205];
long long anss=0;
int N; 
long long Pow(long long x,long long  y){
    long long ans=1;
    while (y){
        if (y&1ll) ans=1ll*ans*x%fish;
        x=1ll*x*x%fish;
        y>>=1ll;
    }
    return ans;
}
long long Gauss(long long n){
    int t=1;
    long long now=1,ans=0;
    for (int i=1;i<=n;i++){
        now=t;
        while (!a[now][i]&&now<=n)
            now++;
        if (now==n+1) continue;
        if (now!=t) swap(a[now],a[t]);
        for (int j=t+1;j<=n;j++){
            if (a[j][i]) a[j]^=a[t];
        }
        ans++;
        t++;
    }
    return n-ans;
}
int main(){
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            scanf("%d",&aa[i][j]);
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            scanf("%d",&b[i][j]);
    for (int i=1;i<=N;i++){
        for (int j=1;j<=N;j++){
            for (int k=1;k<=N;k++){
                a[j][k]=aa[j][k];
            }        
            a[j][j]=(aa[j][j]-b[j][i]+2)%2;
        }    
        long long T=Gauss(1ll*N);
        anss+=T;
    }
    cout<<Pow(2ll,anss);
    return 0;
}

 2019ccpc秦皇岛

D. Decimal

 签到,判断这个数的因子是不是只有$2/5$即可

#include 
using namespace std;
int T,N; 
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        while (N%2==0) N/=2;
        while (N%5==0) N/=5;
        if (N!=1) printf("Yes\n");
        else printf("No\n"); 
    }
    return 0;
}

F. Forest Program

分类讨论。

首先把所有环取出来

发现其实要是森林的话,不能有环

其实就是每个环至少断一个边

对一个有$n$个边的环来说

这个答案是$2^n - 1$

剩下的边随便取

$2^cnt$

怎么找环?

类似tarjan,dfs的时候找到一个访问过的位置大力弹栈就行

因为仙人掌图所以显然是正确的。

代码学长写的

#include 
using namespace std;
const int P= 998244353;
const int N=1e6+10;
int ans=1,cnt=0;
vector<int>E[N];
int vis[N],pre[N];
int power(int x,int y){
        int res=1;
        while(y)
        {
            if (y&1) res=1LL*res*x%P;
            x=1LL*x*x%P;
            y>>=1;
        }
        return res;
    }
void dfs(int u,int f){
           vis[u]=1;
          for(auto v:E[u])
          {
              if(v==f||vis[v]==2) continue;
            if(vis[v]==1)
            {
               int now=u;
               int sz=1;
               while(now!=v)now=pre[now],sz++;
               cnt+=sz;
               ans=(1LL*ans*(power(2,sz)-1)%P+P)%P; 
            }else pre[v]=u,dfs(v,u);
          }
          vis[u]=2;
 }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
 
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
    ans=1LL*ans*power(2,m-cnt)%P;
    cout<'\n';
}

K. MUV LUV UNLIMITED

很有趣的博弈题.jpg

首先,如果一个树全是由偶数链构成,那么显然后手必胜

全是奇数链则先手必胜

考虑奇偶交替的情况

显然,先手可以决策局势

因为我可以把所有的奇数取成偶数

然后就有一个native的想法, 大力考虑所有叶子节点到根的距离的奇偶性,然后全是偶数才后手必胜,否则先手必胜

然后被样例叉出去了(

为什么?

因为路径会有交叉

那么我们就每次考虑一个子问题,即每次考虑一个点,下面挂的全是链

显然这个子情况符合我上面说的东西

那么我们要怎么合并子情况?

实际上还是只有全是偶数的时候后手必胜,因为这时候后手在每一轮子问题里都必胜

否则先手是可以决定到一个子问题的终点的时候自己是先手还是后手的,而这会决定下一个子问题的胜负。

于是做法就是:对所有子问题考虑,如果路径全是偶数的话,那么后手胜利

否则先手必胜。

#include 
using namespace std;
int N,T;
int odd,even;
vector<int> Son[1000005];
void dfs(int Now,int Len,int dep){
    if (Son[Now].size()==0){
        int Lenn=Len-dep;
        if (Lenn&1) odd=1;
        return;
    }
    for (auto x:Son[Now]){
        if (Son[Now].size()>1)
        dfs(x,Len+1,Len);
        else dfs(x,Len+1,dep);
        if (odd) return;
    }
}
int main(){
    scanf("%d",&T);
    while (T--){
        odd=0,even=0;
        scanf("%d",&N);
        for (int i=1;i<=N;i++)
             Son[i].clear();
        for (int i=2;i<=N;i++){
            int fa;
            scanf("%d",&fa);
            Son[fa].push_back(i);
        }
        dfs(1,1,0);
        if (!odd) {
            printf("Meiya\n");
        }
        else printf("Takeru\n");
    }
    return 0;
}

 赛后补题:

E.Escape

核心是发现至多两个机器人经过同一个位置,且这两个机器人的方向一定不同(可以画画图或者反证)

然后发现$n<=100$,我们考虑网络流

把一个位置拆成两个点,横点和竖点

每个点可以向四个方向连一个流量为1的边,表示正常走路

横点竖点间连一个流量为1的边,表示换向。

然后每个终点向$T$连边,流量为$1$,$S$向起点,流量为$1$

代码是赛中队友写的,赛后调了调

赛中没考虑终点能否到达,而且到终点的流量连成了$inf$

#include 
#include 
#include 
using namespace std;
const int N=1e5+10,M=1e6+10,INF=1e9;
int n,m,S,T,cnt;
int head[N],d[N],cur[N];
struct edges
{
    int v,nxt,f;
}e[M*2];
void add(int u,int v,int f)
{
    e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,head[u]=cnt++;
    e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
}
 
bool bfs()
{
    memset(d,-1,sizeof d);
    queue<int>q;
    q.push(S);
    d[S]=0,cur[S]=head[S];
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].nxt)
        {
            int v=e[i].v,f=e[i].f;
            if(d[v]==-1&&f)
            {
                d[v]=d[u]+1;
                cur[v]=head[v];
                if(v==T) return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i&&flowe[i].nxt)
    {
        cur[u]=i;
        int v=e[i].v,f=e[i].f;
        if(d[v]==d[u]+1&&f)
        {
            int t=find(v,min(f,limit-flow));
            if(!t) d[v]=-1;
            e[i].f-=t,e[i^1].f+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int ans=0,flow;
    while(bfs()) while(flow=find(S,INF)) ans+=flow;
    return ans;
}
int x[105][105],y[105][105];
char g[105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        memset(head,-1,sizeof head);
        cnt=0;
        int a,b;
        cin>>n>>m>>a>>b;
        S=0,T=n*m*2+1;
        int idx=0;
        for(int i=1;i<=n;i++)
        cin>>g[i]+1;
 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) x[i][j]=++idx,y[i][j]=++idx;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(g[i][j]=='1') continue; 
                if(j-1>0&&g[i][j-1]=='0') add(x[i][j],x[i][j-1],1);
                if(j+1<=m&&g[i][j+1]=='0') add(x[i][j],x[i][j+1],1);
                if(i-1>0&&g[i-1][j]=='0') add(y[i][j],y[i-1][j],1);
                if(i+1<=n&&g[i+1][j]=='0') add(y[i][j],y[i+1][j],1);
                add(x[i][j],y[i][j],1);
                add(y[i][j],x[i][j],1);
            }
        for(int i=1;i<=a;i++) 
        {
            int x;
            cin>>x;
            if(g[1][x]=='1') continue;
            add(S,y[1][x],1);
        }
        for(int i=1;i<=b;i++)
        {
            int x;
            cin>>x;
            if(g[n][x]=='1') continue;
            add(y[n][x],T,1);
        }
    
        if(dinic()"No";
        else cout<<"Yes";
        cout<<'\n';
    }
    
    
G. Game on Chessboard 我不理解( 为什么TLE  on test6 卡了半天常数过不去,重构一下过了   发现$n$非常的小,考虑状压 然后这种左下角全空的考虑插头$dp$ 转移应该挺裸的,枚举一个位置或者两个位置一起消 重点是要发现优先两个一起消去
#include 
using namespace std;
int dp[1<<24],N;
int w[12][12];
char a[12][12];
int main(){
    scanf("%d",&N);
    for (int i=0;i)
        scanf("%s",a[i]);
    for (int i=0;i)
        for (int j=0;j)
            scanf("%d",&w[i][j]);
    int T=(1<1;
    int S=(T<<N);
    for (int i=T;i<=S;i++) dp[i]=1e9;
    dp[S]=0;
    for (int st=S;st>T;st--){
        if (dp[st]==1e9) continue;
        int cnt=0;
        for (int i=0;i<=2*N;i++)
            if (st>>i&1) cnt++;
        if (cnt!=N) continue;
        int x=-1,y=0;
        for (int i=2*N-1;i>=1;i--){
            if ((st>>i)&1) x++;
            else y++;
            if ((st>>i)&1 && !((st>>(i-1))&1)){
                dp[st-(1<<(i-1))]=min(dp[st-(1<<(i-1))],dp[st]+(a[x][y]!='.')*w[x][y]);
                int nx=-1,ny=0;
                for (int j=2*N-1;j>i+1;j--){
                    if ((st>>j)&1) nx++;
                        else ny++;
                    if (((st>>j)&1) && (!((st>>(j-1))&1)) && (a[x][y] + a[nx][ny] == 'B' + 'W')){
                        dp[st-(1<<(i-1))-(1<<(j-1))]=min(dp[st-(1<<(i-1))-(1<<(j-1))],dp[st]+abs(w[x][y]-w[nx][ny]));
                    }
                }
            }
        }
    }
    cout<<dp[T];
    return 0;
}

 icpc2020首尔

B. Commemorative Dice

签到,暴力枚举

C. Dessert Café

因为两点之间在树上只有一条路径,稍微画画图就会发现答案的点其实就是关键点之间的点。

#include 
using namespace std;
int ans=0;
int N,K;
int pd[100005],cnt,Arrive[200005],nex[200005],las[200005];
bool col[200005];
void dfs(int Now,int fa){
    int cnt=0,cnt1=0;
    for (int i=las[Now];i;i=nex[i]){
        int v=Arrive[i];
        if (v==fa) continue;
        dfs(v,Now);
        pd[Now]+=pd[v];
        if (pd[v]) cnt++;
    }
    if (col[Now]) pd[Now]++;
    if (K-pd[Now]!=0) cnt++;
    if (cnt>=2||col[Now]) ans++;
}
void jt(int x,int y){
    cnt++;
    nex[cnt]=las[x];
    las[x]=cnt;
    Arrive[cnt]=y;
}
int main(){
    scanf("%d%d",&N,&K);
    for (int i=1;i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        jt(u,v);
        jt(v,u); 
    }
    for (int i=1;i<=K;i++){
        int x;
        scanf("%d",&x);
        col[x]=true;
    }
    dfs(1,1);
    printf("%d\n",ans);
    return 0;
}

G. Mobile Robot

固定起点后,每个点都确定了,每个点还是会走到它对应的那个位置上去

考虑从起点向右延伸,则对于每个点来说,它走的距离就是$|x+(i-1)*d - pos_i|$

$x$是我们的起点

$|x-(pos_i-(i-1)*d)|$

最小化这个的最大值

我们转化一下,其实就是有$n$个新点,每个点是$pos_i-(i-1)*d$,找一个点$x$到最离它远点距离最近

显然是区间中点。

左延伸类似的做。

注意精度。

#include 
using namespace std;
int N;
long long pos[1000005],d;
long long pos1[1000005],pos2[1000005];
int main(){
    scanf("%d%lld",&N,&d);
    for (int i=1;i<=N;i++){
        scanf("%lld",&pos[i]);
        pos1[i]=pos[i]-(i-1)*d;
        pos2[i]=pos[i]+(i-1)*d;
    }
    sort(pos1+1,pos1+N+1);
    sort(pos2+1,pos2+N+1); 
    long long ans1=0;
    ans1=(pos1[N]-pos1[1])/2;
    long long anss=(pos2[N]-pos2[1])/2;
    long long Ans;
    int flag=0;
    if (anss<ans1){
        Ans=anss;
        if ((pos2[N]-pos2[1])%2==0) flag=0;
        else flag=1;
    }
    else{
        Ans=ans1;
        if ((pos1[N]-pos1[1])%2==0) flag=0;
        else flag=1;
    }
    printf("%lld.%d\n",min(anss,ans1),flag*5);
    return 0;
}

H. Needle

转化一下式子,统计$2x_2=x1+x3$的三元组$(x_1,x_2,x_3)$

考虑固定$2*x_2$

$\sum f(x)*g(y),xy=2x_2$

$fft$即可。

//#pragma GCC optimize(2)
#include 
#define ll long long
#define pb push_back
using namespace std;

const int N = 1100000;
const int p = 998244353, gg = 3, ig = 332738118, img = 86583718;//1004535809 
const int M=18e5;
const int mod=998244353;
template void rd(T &x)
{
    x = 0;
     int f = 1;
     char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    x *= f;
}

ll qpow(ll a, int b)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

namespace Poly
{
    #define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
    #define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
    #define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
    #define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了

    typedef vector poly;
    const int G = 3;//根据具体的模数而定,原根可不一定不一样!!!
    //一般模数的原根为 2 3 5 7 10 6
    const int inv_G = qpow(G, mod - 2);
    int RR[N], deer[2][21][N], inv[N];

    void init(const int t) {//预处理出来NTT里需要的w和wn,砍掉了一个log的时间
        for(int p = 1; p <= t; ++ p) {
            int buf1 = qpow(G, (mod - 1) / (1 << p));
            int buf0 = qpow(inv_G, (mod - 1) / (1 << p));
            deer[0][p][0] = deer[1][p][0] = 1;
            for(int i = 1; i < (1 << p); ++ i) {
                deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//
                deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
            }
        }
        inv[1] = 1;
        for(int i = 2; i <= (1 << t); ++ i)
            inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    }

    int NTT_init(int n) {//快速数论变换预处理
        int limit = 1, L = 0;
        while(limit < n) limit <<= 1, L ++ ;
        for(int i = 0; i < limit; ++ i)
            RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
        return limit;
    }

    void NTT(poly &A, int type, int limit) {//快速数论变换
        A.resize(limit);
        for(int i = 0; i < limit; ++ i)
            if(i < RR[i])
                swap(A[i], A[RR[i]]);
        for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
            int len = mid >> 1;
            for(int pos = 0; pos < limit; pos += mid) {
                int *wn = deer[type][j];
                for(int i = pos; i < pos + len; ++ i, ++ wn) {
                    int tmp = 1ll * (*wn) * A[i + len] % mod;
                    A[i + len] = ck(A[i] - tmp + mod);
                    A[i] = ck(A[i] + tmp);
                }
            }
        }
        if(type == 0) {
            for(int i = 0; i < limit; ++ i)
                A[i] = 1ll * A[i] * inv[limit] % mod;
        }
    }

    inline poly poly_mul(poly A, poly B) {//多项式乘法
        int deg = A.size() + B.size() - 1;

        int limit = NTT_init(deg);

        poly C(limit);
        NTT(A, 1, limit);
        NTT(B, 1, limit);
        for(int i = 0; i < limit; ++ i)
            C[i] = 1ll * A[i] * B[i] % mod;
        NTT(C, 0, limit);
        C.resize(deg);
        return C;
    }
    //多个多项式相乘CDQ或者利用优先队列启发式合并
    /*
    inline poly CDQ(int l,int r)
    {
      if(l==r)
      { 
        return poly{1,A[l]};
      }
      int mid=l+r>>1;
      poly L=CDQ(l,mid);
      poly R=CDQ(mid+1,r);
      return poly_mul(L,R);  
    }*/
}

using namespace Poly;
const int del=30000;
poly A(60005),B(120005),C(60005);
int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);

    init(19);
    
    int n1,n2,n3;
    cin>>n1;
    for(int i=1;i<=n1;i++)
    {
        int x;
        cin>>x;
        A[x+del]=1;
    }
    cin>>n2;
    for(int i=1;i<=n2;i++)
    {
        int x;
        cin>>x;
        B[2*(x+del)]=1;
    }
    cin>>n3;
    for(int i=1;i<=n3;i++)
    {
        int x;
        cin>>x;
        C[x+del]=1;
    }
    

    poly D=poly_mul(A,C);

    int res=0;
   
    for(int i=0;i<120001;i++)
    if(D[i]!=0&&B[i]) res+=D[i];
    cout<'\n';
    
    return 0;

}