ACM训练联盟周赛(第一场)

时间:2023-01-09 09:47:52

B:Zeratul与Xor

题目描述

Xor(按位异或),对应C++中的“^”运算符。

Zeratul给出了一个数列A[n](n≤105),要做q(q≤105)组动作,这些动作包括:

1  a:数列中所有的元素异或上a。a非负,且不会超过int的范围。

2  b:向数列尾部添加一个新的数b。b非负,且不会超过int的范围

3  k:查询当前的数列中第k小的数,并输出这个数。保证k不会超过当前数列的长度。

输入

第一行包括两个元素n,q(1≤n≤1051≤q≤1)

第二行包括n个数,代表初始的数列。数列中的所有元素非负,且不会超过int的范围。

接下来q行,代表q组动作,含义见描述。

输出

对于每组需要输出的动作,输出一行代表答案。输入数据保证动作中至少有一组需要输出的动作。

输出时每行末尾的多余空格,不影响答案正确性

样例输入

3 3
1 2 3
1 2
2 2
3 3

样例输出

2
字典树+dfs,区间第k小就是第(n-k+1)大
异或满足结合律
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <ext/rope>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266560
#define mem(a) (memset(a,0,sizeof(a)))
int dcmp(double x){return fabs(x)<esp?0:x<0?-1:1;}
typedef long long ll;
const int maxn=1e7+10;
int tree[maxn][2],pos=0;
int val[maxn],n,m,x,p,ans=0;
void insert(int n,int root)
{//求第k大,从最高位开始判断,倒着插
    for(int i=31;i>=0;i--)
    {
        int x=n&(1<<i)?1:0;
        if(tree[root][x]==-1)
            tree[root][x]=++pos;
        root=tree[root][x];
        val[root]++;
    }
}
//异或取相反
int query(int root,int bit,int k,int now)
{
    if(bit==-1) return 0;
    int x=now&(1<<bit)?1:0;
    if(x==0)//相反数为1
    {
        if(tree[root][x^1]!=-1 && val[tree[root][x^1]]>=k)
            return (1<<bit)+query(tree[root][x^1],bit-1,k,now);//此位为1,并且数量足够可取,1位加
        else{
            if(tree[root][x^1]!=-1) return query(tree[root][x],bit-1,k-val[tree[root][x^1]],now);//1位不够,0位补充,0位不加
            else return query(tree[root][x],bit-1,k,now);//0位
        }
    }
    else//相反数为0
    {
        if(tree[root][x^1]!=-1 && val[tree[root][x^1]]>=k) 
            return query(tree[root][x^1],bit-1,k,now);//0位,不加
        else{
            if(tree[root][x^1]!=-1) return (1<<bit)+query(tree[root][x],bit-1,k-val[tree[root][x^1]],now);//1位,加
            else return (1<<bit)+query(tree[root][x],bit-1,k,now);//1位,加
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(tree,-1,sizeof(tree));
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        insert(x,0);
    }
    while(m--)
    {
        scanf("%d%d",&p,&x);
        if(p==1) ans^=x;
        else if(p==2) insert(ans^x,0),n++;
        else printf("%d\n",query(0,31,n-x+1,ans)^ans);//区间第k小就是第(n-k+1)大
    }
    return 0;
}

C. Alice和Bob的Nim游戏

题目描述

众所周知,Alice和Bob非常喜欢博弈,而且Alice永远是先手,Bob永远是后手。

Alice和Bob面前有3堆石子,Alice和Bob每次轮流拿某堆石子中的若干个石子(不可以是0个),拿到所有石子中最后一个石子的人获胜。这是一个只有3堆石子的Nim游戏。

Bob错误的认为,三堆石子的Nim游戏只需要少的两堆的石子数量加起来等于多的那一堆,后手就一定会胜利。所以,Bob把三堆石子的数量分别设为 {k,4k,5k}(k>0)。

现在Alice想要知道,在k 小于 2^n 的时候,有多少种情况先手一定会获得胜利。

输入

一个整数n(1≤n≤2×109)。

输出

 输出先手胜利的可能情形数。答案对109+7取模。

输出时每行末尾的多余空格,不影响答案正确性

样例输入

3

样例输出

2
我们可以求出先手必胜局面k^4k^5k=0;所以,所有后手获胜的k必须满足二进制位形如10010或10011的形式(k和k左移两位1不重合)
设f(n)表示小于2^n(即二进制第n位为0)的满足上述条件的k的个数,则f(n)= f(n-1)+ f(n-3)+ f(n-4)+ 2。
矩阵快速幂
f[n] 1 0 1 1 1 f[n-1]
f[n-1] 1 0 0 0 0 f[n-2]
f[n-2] 0 1 0 0 0 f[n-3]
f[n-3] 0 0 1 0 0 f[n-4]
2 0 0 0 0 1 2
f[1]=1,f[2]=3,f[3]=5,f[4]=8;

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <ext/rope>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266560
#define mem(a) (memset(a,0,sizeof(a)))
int dcmp(double x){return fabs(x)<esp?0:x<0?-1:1;}
typedef long long ll;
ll n;
struct matrix
{
    ll a[5][5];
    matrix(){
        memset(a,0,sizeof(a));
    }
};
matrix multiply(matrix ans,matrix pos)
{
    matrix res;
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            for(int k=0;k<5;k++)
                res.a[i][j]=(res.a[i][j]+ans.a[i][k]*pos.a[k][j])%MOD;
    return res;
}
matrix matrix_pow(ll n)
{
    matrix ans,pos;
    pos.a[0][0]=pos.a[0][2]=pos.a[0][3]=pos.a[0][4]=1;
    pos.a[1][0]=pos.a[2][1]=pos.a[3][2]=pos.a[4][4]=1;
    for(int i=0;i<5;i++)
        ans.a[i][i]=1;
    while(n)
    {
        if(n&1) ans=multiply(ans,pos);
        n>>=1;
        pos=multiply(pos,pos);
    }
    return ans;
}
ll quick_pow(ll x,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=(ans*x)%MOD;
        n>>=1;
        x=(x*x)%MOD;
    }
    return ans%MOD;
}
int main()
{
    scanf("%lld",&n);
    if(n<=2) return 0*printf("0\n");
    else if(n==3) return 0*printf("2\n");
    else if(n==4) return 0*printf("7\n");
    matrix pos=matrix_pow(n-4);
    ll ans=(pos.a[0][0]*8+pos.a[0][1]*5+pos.a[0][2]*3+pos.a[0][3]+pos.a[0][4]*2)%MOD;
    printf("%lld\n",(quick_pow(2,n)-1+MOD-ans+MOD)%MOD);
    return 0;
}

D. 薇尔莉特的委托

薇尔莉特是一名非常敬业的自动手记人偶,经常需要上门为客人写信,所以她经常穿梭在大陆的各个城市之间,完成委托。

 

薇尔莉特生活的是一片刚刚结束战乱的大陆,连接各个城市的只有几条铁路线,其中一些还经常被反叛军残党破坏,所以尽管她是一位非常敬业的人偶,有时候工作上也会感到力不从心。

 

薇尔莉特每天都会接到许多来自不同的地方的委托,她可以在黎明时分乘坐敞篷飞机来到大陆上任何一个城市,但是接下来,她就只能乘坐火车去完成其他城市的委托了。

 

大陆上有n座城市,有m条连接两个城市的铁路,薇尔莉特会告诉你m行铁路的信息,每行两个数字x,y代表第i条铁路连接的两个城市的编号,并且她是按一定顺序告诉你的(据说是少佐告诉她的顺序)。

 

每天黎明,薇尔莉特开始工作前,反叛军都会破坏掉一些铁路。反叛军残党的首领是个强迫症,他知道薇尔莉特告诉你的铁路线的顺序,所以他决定破坏薇尔莉特告诉你的第L条到第R条铁路,共(R-L+1)条。

 

每天深夜,薇尔莉特结束工作后,*都会检修铁路,把所有被破坏的铁路修好

 

为了最大程度上满足客人的需要,薇尔莉特想请你帮她计算一下,她每天工作时间最多能去多少个城市完成委托。特别的,完成委托和路上的时间可以忽略,所以你只需求出大陆抽象出的图上,最大的连通块有多少个点即可。

 

输入

 

第一行两个整数n,m,意义见描述第4段

 

接下来的m行每行两个整数x,y,意义见描述第4段

 

本题中铁路是双向的

 

接下来一行一个整数d,表示天数。

 

接下来的d行,每行两个整数L,R,表示反叛军当天要破坏第L条到第R条铁路。

 

数据保证:1≤n≤1031≤m≤1041≤x,y≤n1≤L,R≤m1≤d≤2×104

 

输出

 

d行,每行一个整数,表示当天薇尔莉特最多能完成多少个城市的委托(即最大连通块的点数)。

 

SOURCEcodeforces

 

输出时每行末尾的多余空格,不影响答案正确性

 

样例输入

6 6
1 2
5 4
2 3
3 1
3 6
4 6
6
1 3
2 5
1 6
5 5
2 4
4 4

样例输出

4
2
1
3
3
6
双向并查集,好题,给个赞
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
int dcmp(double x){return fabs(x)<esp?0:x<0?-1:1;}
typedef long long ll;
struct dsu{
    int f[1006];
    void init(){
        for(int i=0;i<=1000;i++)
            f[i]=i;
    }
    int find(int x){
        return f[x]==x?x:f[x]=find(f[x]);
    }
    void join(int x,int y){
        int xx=find(x);
        int yy=find(y);
        if(xx!=yy) f[xx]=yy;
    }
}l[10006],r[10006];
int u[10006],v[10006],n,m,k,vis[1006];
void solve(dsu l,dsu r,int n){
    for(int i=1;i<=n;i++)
        l.join(i,r.find(i));
    int ans=-1;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        int x=l.find(i);
        vis[x]++;
        ans=max(ans,vis[x]);
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&u[i],&v[i]);
    l[0].init();
    r[m+1].init();
    for(int i=1;i<=m;i++)
    {//前缀并查集
        l[i]=l[i-1];
        l[i].join(u[i],v[i]);
    }
    for(int i=m;i;i--)
    {//后缀并查集
        r[i]=r[i+1];
        r[i].join(u[i],v[i]);
    }
    scanf("%d",&k);
    while(k--){
        int x,y;
        scanf("%d%d",&x,&y);
        solve(l[x-1],r[y+1],n);
    }
    return 0;
}

 

 

G. 算个欧拉函数给大家助助兴

题目描述

木南有一天学习了欧拉函数,知道了对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目。那么他定义f(n)为有多少个小于等于n的数可以整除n。

例如f(4)=3。(可以被1,2,4整除)。

那么你可以写个程序计算一下f(n)吗?

输入

输入一个n  n≤1018

输出

输出f(n)

输出时每行末尾的多余空格,不影响答案正确性

样例输入

999999999999999989

样例输出

2
求一根数有多少个因子,大数素因子分解
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
#include <bitset>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define set_bit(x,ith,bool) ((bool)?((x)|(1<<(ith))):((x)&(~(1<<ith))))
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef unsigned long long ull;
typedef long long ll;
const int s=8;
char ch[26];
ll mult_mod(ll a,ll b,ll c)
{
    a%=c;
    b%=c;
    ll ret=0;
    ll tmp=a;
    while(b)
    {
        if(b&1){
            ret+=tmp;
            if(ret>c) ret-=c;
        }
        tmp<<=1;
        if(tmp>c) tmp-=c;
        b>>=1;
    }
    return ret;
}
ll pow_mod(ll a,ll n,ll mod)
{
    ll ans=1;
    ll tmp=a%mod;
    while(n)
    {
        if(n&1) ans=mult_mod(ans,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ans;
}
bool check(ll a,ll n,ll x,ll t)
{
    ll ret=pow_mod(a,x,n);
    ll last=ret;
    for(int i=1;i<=t;i++)
    {
        ret=mult_mod(ret,ret,n);
        if(ret==1 && last!=1 && last!=n-1) return true;
        last=ret;
    }
    if(ret!=1) return true;
    else return false;
}
bool miller_pabin(ll n)
{
    if(n<2) return false;
    if(n==2) return true;
    if((n&1)==0) return false;
    ll x=n-1;
    ll t=0;
    while((x&1)==0) {x>>=1;t++;}
    srand(time(NULL));
    for(int i=0;i<s;i++){
        ll a=rand()%(n-1)+1;
        if(check(a,n,x,t)) return false;
    }
    return true;
}
ll factor[110];
int tol=0;
ll gcd(ll a,ll b)
{
    ll t;
    while(b)
    {
        t=a;
        a=b;
        b=t%b;
    }
    if(a>=0) return a;
    else return -a;
}
ll pollard_rho(ll x,ll c)
{
    ll i=1,k=2;
    srand(time(NULL));
    ll x0=rand()%(x-1)+1;
    ll y=x0;
    while(1)
    {
        i++;
        x0=(mult_mod(x0,x0,x)+c)%x;
        ll d=gcd(y-x0,x);
        if(d!=1 && d!=x) return d;
        if(y==x0) return x;
        if(i==k){y=x0;k+=k;}
    }
}
void findfac(ll n,ll k)
{
    if(n==1) return ;
    if(miller_pabin(n))
    {
        factor[tol++]=n;
        return ;
    }
    ll p=n;
    ll c=k;
    while(p>=n) p=pollard_rho(p,c--);
    findfac(p,k);
    findfac(n/p,k);
}
int main()
{
    ll n;
    scanf("%lld",&n);
    if(miller_pabin(n)) printf("2\n");
    else
    {
        findfac(n,107);
        ll ans=1;
        for(int i=0;i<tol;i++)
        {
            //printf("%lld ",factor[i]);
            ll pos=0;
            while(n>0 && (n%factor[i]==0))
            {
                pos++;
                n/=factor[i];
            }
           // printf("%lld %lld\n",factor[i],pos);
            if(pos) ans*=(pos+1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

M. Big brother said the calculation

 

题目描述

(我们永远的)大哥有很多的小弟(n个)。每一个小弟有一个智力值。现在小弟们聚集在了大哥身旁,排成了一队,等待大哥的检阅。n个小弟的智力值是一个1到n的排列。

大哥在检阅小弟时,每次会选择一些相邻的小弟,让他们按照自己的智力值从小到大或从大到小顺序重新排队(没有被选择的小弟位置不变),以便他排除其中的二五仔。

在大哥检阅完小弟之后,老仙突然来了。他十分想为难一下大哥,所以他问大哥其中某一个小弟的智力值是多少。大哥十分的慌,并不能回答这个问题,所以让你来帮他解决这个问题。如果你能够解决,大哥可能会赠与你守护者的三叉戟和并教你他的换家绝学。

输入

第一行3个整数n,q,k,表示小弟的数目,大哥检阅小弟时让一些小弟重新排队的次数,以及最后老仙问他的是第几个小弟的智力值。

第二行n(1≤n≤105)个整数,表示每个小弟的智力值,保证符合题意,是1到n的一个排列。

接下来q(1≤q≤105)行,每行3个整数a,b,t(1≤a≤b≤n,0≤t≤1),表示他选择了第a个到第b个小弟(a,b均包含)进行重新排列。若t=0,则为从小到大;若t=1,则为从大到小。

输出

输出一个整数,代表在检阅之后第k个小弟的智力值是多少。

输出时每行末尾的多余空格,不影响答案正确性

样例输入

5 2 4
1 4 3 2 5
1 3 0
3 5 1

样例输出

4
线段树+二分
首先,题目确定是关于n的一个排列,那么二分k处可能取的值,然后构建线段树时,大于他标记为1,小于他标记为0,每次查找要更新的区间有多少个一,在全部标记为0
操作为1是把这些1放到此区间左边,操作为0放到此区间右边,然后查找时,若k处为1,说明这里的数一定大于二分出来的数,不满足,继续二分。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <ext/rope>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266560
#define mem(a) (memset(a,0,sizeof(a)))
int dcmp(double x){return fabs(x)<esp?0:x<0?-1:1;}
typedef long long ll;
const int maxn=100005;
int n,m,a[maxn],operation[maxn],k;
int li[maxn],ri[maxn];
struct tree{
    int l,r;
    int sum,lazy;
}tree[maxn<<2];
void pushdown(int root){
    if(tree[root].lazy!=-1){
        tree[root<<1].lazy=tree[root].lazy;
        tree[root<<1|1].lazy=tree[root].lazy;
        tree[root<<1].sum=tree[root].lazy*(tree[root<<1].r-tree[root<<1].l+1);
        tree[root<<1|1].sum=tree[root].lazy*(tree[root<<1|1].r-tree[root<<1|1].l+1);
        tree[root].lazy=-1;
    }
}
void pushup(int root){
    tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
}
void build(int l,int r,int root,int val)
{
    tree[root].l=l;tree[root].r=r;
    tree[root].lazy=-1;
    if(l==r){
        tree[root].sum=(a[l]>val)?1:0;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1,val);
    build(mid+1,r,root<<1|1,val);
    pushup(root);
}
void update(int L,int R,int val,int root)
{
    if(L<=tree[root].l && R>=tree[root].r){
        tree[root].sum=val*(tree[root].r-tree[root].l+1);
        tree[root].lazy=val;
        return ;
    }
    pushdown(root);
    int mid=tree[root].l+tree[root].r>>1;
    if(L<=mid) update(L,R,val,root<<1);
    if(R>mid) update(L,R,val,root<<1|1);
    pushup(root);
}
int query(int L,int R,int root){
    if(L<=tree[root].l && R>=tree[root].r){
        return tree[root].sum;
    }
    pushdown(root);
    int mid=tree[root].l+tree[root].r>>1;
    int ans=0;
    if(L<=mid) ans+=query(L,R,root<<1);
    if(R>mid) ans+=query(L,R,root<<1|1);
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&li[i],&ri[i],&operation[i]);
    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        build(1,n,1,mid);
        for(int i=0;i<m;i++)
        {
            int L=li[i];
            int R=ri[i];
            int c=query(L,R,1);
            update(L,R,0,1);
            if(operation[i] && L<=L+c-1) update(L,L+c-1,1,1);
            else if(!operation[i] && R>=R-c+1) update(R-c+1,R,1,1);
        }
        if(query(k,k,1)) l=mid+1;
        else r=mid;
    }
    printf("%d\n",l);
    return 0;
}