头像

cjlworld




离线:6小时前


活动打卡代码 AcWing 2268. 时态同步

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=2e6+5;

int one[N],idx;
int ver[N],Next[N],edge[N];
inline void AddEdge(int a,int b,int c)
{
    Next[idx]=one[a],ver[idx]=b,edge[idx]=c,one[a]=idx++;
}


LL f[N];
LL ans;

void dfs(int x,int fa)
{
    for(int i=one[x],y;~i;i=Next[i]) {
        y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
        f[x]=max(f[x],f[y]+edge[i]);
    }
    for(int i=one[x],y;~i;i=Next[i]) {
        y=ver[i];
        if(y==fa) continue;
        ans+=f[x]-f[y]-edge[i];
    }
}

int n,rt;

int main()
{
//  freopen("1.in","r",stdin);
    int i;
    int x,y,z;

    scanf("%d%d",&n,&rt);
    memset(one,-1,sizeof one);
    for(i=1;i<=n-1;i++) {
        scanf("%d%d%d",&x,&y,&z);
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }

    dfs(rt,0);
    cout<<ans<<endl;
    return 0;
}



活动打卡代码 AcWing 1412. 邮政货车

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

string f[1024]= {
    "0",
    "0",
    "2",
    "4",
    "12",
    "28",
    "74",
    "184",
    "472",
    "1192",
    "3034",
    "7692",
    "19540",
    "49588",
    "125906",
    "319600",
    "811376",
    "2059728",
    "5228914",
    "13274132",
    "33698012",
    "85546188",
    "217169050",
    "551308584",
    "1399560904",
    "3552947064",
    // 此处省略,可见 https://github.com/cjlworld/OJ/blob/master/acw%231412x.cpp
};
int main()
{
    int n;
    cin>>n;
    cout<<f[n];
    return 0;
}

感觉分类讨论比 插头 Dp 还麻烦。

#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int M=2e5+5;

vector<int> add(vector<int> a,vector<int> b)
{
    vector<int> c;
    int t=0;
    if(a.size()<b.size()) swap(a,b);
    for(int i=0;i<(int)a.size();i++) {
        t+=a[i];
        if(i<(int)b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t) c.push_back(t);
    return c;
}

void output(vector<int> a)
{
    for(int i=a.size()-1;i>=0;i--) 
        putchar(a[i]+'0');
}

int h[2][M]; // 滚动的哈希表 
vector<int> v[2][M];

int q[2][M],cnt[2]; // 滚动的队列,保存哈希表内插入的数的集合。 

int Hash(int cur,int k)
{
    int t=k%M;
    while(h[cur][t]!=-1 && h[cur][t]!=k) 
        if(++t==M) t=0;
    return t;
}

void insert(int cur,int state,vector<int> w)
{
    int t=Hash(cur,state);
    if(h[cur][t]==-1) {
        h[cur][t]=state;
        v[cur][t]=w;
        q[cur][++cnt[cur]]=t;
    }   
    else v[cur][t]=add(v[cur][t],w);
}

int get(int state,int k) // 返回 state 在四进制表示下第 k 位的数 (k 从 0 开始)。 
{
    return state>>(k*2)&3;
}
int set(int k,int v) // 构造一个第 k 位 是 v,其余位是 0 的数。 
{
    return v * (1<<k*2);
}

int n,m; 
int a[1024][20]; // 保存棋盘的信息。
// tips : 能走的设成 1 , 不能走的为 0 , 这样刚好边界也是不可走的。

int main()
{
//  freopen("1.in","r",stdin);
    int i,j,k;
    int x,y;

    scanf("%d",&n); m=4;
    for(i=1;i<=n;i++) 
        for(j=1;j<=m;j++) 
            a[i][j]=1;

    int cur=0,lt,state;
    vector<int> w; w.push_back(1);
    vector<int> ans; ans.push_back(0);
    memset(h,-1,sizeof h);
    insert(cur,0,w);
    for(i=1;i<=n;i++) {
        // 把所有状态左移 1 位 (4 进制)
        // 因为上一行的最后一个变成当前行的第一个,并且 上一行的最后一个 肯定为 0。  
        for(j=1;j<=cnt[cur];j++)
            h[cur][q[cur][j]]<<=2;

        // 枚举每一个格子 (阶段) 
        for(j=1;j<=m;j++) {
            lt=cur,cur^=1; // 滚动 

            cnt[cur]=0; // 清空队列和哈希表!! 
            memset(h[cur],-1,sizeof h[cur]);

            // 枚举上一个阶段的每一个状态,并转移。
            for(k=1;k<=cnt[lt];k++) {

                state=h[lt][q[lt][k]],w=v[lt][q[lt][k]];
                x=get(state,j-1),y=get(state,j);

                if(!a[i][j]) { // 如果当前的格子不能走.
                    // 那么只有没有走的状态有用。 
                    if(x==0&&y==0) insert(cur,state,w);
                }
                // 否则当前格子就是可以走。

                else if(x==0&&y==0) {
                    if(a[i+1][j]&&a[i][j+1])
                        insert(cur,state+set(j-1,1)+set(j,2),w);
                    // 新增两个往 下面 和 右边 走的回路。 
                }
                else if(x!=0&&y==0) {
                    if(a[i+1][j]) insert(cur,state,w); // 往下面走。 
                    if(a[i][j+1]) insert(cur,state-set(j-1,x)+set(j,x),w); // 往右边走。 
                }
                else if(x==0&&y!=0) {
                    if(a[i+1][j]) insert(cur,state-set(j,y)+set(j-1,y),w); // 往下面走。 
                    if(a[i][j+1]) insert(cur,state,w); // 往右边走。 
                }
                else if(x==1&&y==1) {
                    for(int u=j+1,s=1;u<=m;u++) { // 找到 j 匹配的右括号。 
                        if(get(state,u)==1) s++;
                        else if(get(state,u)==2) {
                            s--;
                            if(s==0) {
                                insert(cur,state-set(j-1,1)-set(j,1)-set(u,2)+set(u,1),w); // 找到了。 
                                break;
                            }
                        }
                    }
                }
                else if(x==2&&y==1) insert(cur,state-set(j-1,x)-set(j,y),w);
                else if(x==2&&y==2) {
                    for(int u=j-2,s=1;u>=1;u--) {
                        if(get(state,u)==2) s++;
                        else if(get(state,u)==1) {
                            s--;
                            if(s==0) {
                                insert(cur,state-set(j-1,2)-set(j,2)-set(u,1)+set(u,2),w);
                                break;
                            }
                        } 
                    }
                }
                else if(x==1&&y==2) { // 终结 
                    if(i==n&&j==m)
                        ans=add(ans,w);
                }
            }   
        }
    }
    ans=add(ans,ans);
    output(ans);
    return 0;
}



活动打卡代码 AcWing 2154. 梦幻布丁

这个 swap(p[x],p[y]) 太漂亮了吧!

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=2e6+5;

int p[N]; // p[i] 表示 i 实际被染成的颜色。 

int one[N],idx;
int ver[N],Next[N];
stack<int> S;

inline void DelEdge(int id) { S.push(id); }
inline int NewId() 
{
    if(S.size()) {
        int res=S.top();
        S.pop();
        return res;
    }
    else return ++idx;
}
inline void AddEdge(int a,int b)
{
    int cur=NewId();  
    Next[cur]=one[a]; ver[cur]=b; one[a]=cur;
}

int n,m;
int a[N];
int cnt[N];

int ans;

inline void turn(int pos,int col) 
{
    if(a[pos]==col) return;
    cnt[a[pos]]--,cnt[col]++;
    if((pos>1 && a[pos-1]==a[pos]) || pos==1) ans++; // 先变成一个与所有颜色都不同的颜色。 
    if((pos<n && a[pos+1]==a[pos]) || pos==n) ans++;
    a[pos]=col;
    if((pos>1 && a[pos-1]==a[pos]) || pos==1) ans--; // 再还原。 
    if((pos<n && a[pos+1]==a[pos]) || pos==n) ans--;
}

int main()
{
//  freopen("1.in","r",stdin);
    int i;
    int opt,x,y;

    for(i=0;i<N;i++) p[i]=i;

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        AddEdge(a[i],i);
        cnt[a[i]]++;
    }

    ans=1;
    for(i=2;i<=n;i++) 
        if(a[i]!=a[i-1]) ans++;

    while(m--) {
        scanf("%d",&opt);
        if(opt==1) {
            scanf("%d%d",&x,&y);
            if(p[x]==p[y] || cnt[p[x]]==0) continue;
            if(cnt[p[x]]>cnt[p[y]]) swap(p[x],p[y]);
            // 这一步是把 y 表示的颜色变成 x 表示的颜色。
            // x 表示的颜色变成原来 y 表示的颜色。
            // 问题又被化为 cnt[p[y]]>cnt[p[x]] && 要把 a[] 中值为 p[x] 的数变成 p[y]。 

            // 注意这一步不能用并查集来写,因为把 y 变成 x 之后,还可以把颜色变成 y .
            // 也就是 y 这个编号还是有用的。 
            for(i=one[p[x]];i;i=Next[i]) {
                AddEdge(p[y],ver[i]);
                turn(ver[i],p[y]);
            }
            for(i=one[p[x]];i;i=Next[i]) DelEdge(i); // 注意顺序,不能还在用的时候就删除。 
            one[p[x]]=0;
        }
        else printf("%d\n",ans);
    }

    return 0;
}

然后还可以直接把一条链拉到 p[y] 上。

    for(i=one[p[x]];~i;i=Next[i]) {
        turn(ver[i],p[y]);
        if(Next[i]==-1) {
            Next[i]=one[p[y]],one[p[y]]=one[p[x]];
            // 注意 one[p[y]]=one[p[x]] 也要放在里面。
            // 否则要特判 one[p[x]] 里一个数也没有的情况。
            break;
        }
    }
    one[p[x]]=-1;

这样就不用动态开点了。



活动打卡代码 AcWing 158. 项链

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

string minshow(string s)
{
    string ss=s+s;
    int i=0,j=1,k,len=s.length();
    while(i<len&&j<len) {
        for(k=0;k<len&&ss[i+k]==ss[j+k];k++);
        if(k==len) break;
        if(ss[i+k]>ss[j+k]) {
            i+=k+1;
            if(i==j) i++;
        }
        else {
            j+=k+1;
            if(i==j) j++;
        }
    }
    return ss.substr(min(i,j),len);
}

int main()
{
//  freopen("1.in","r",stdin);
    string a,b;
    cin>>a>>b;
    a=minshow(a),b=minshow(b);
//  printf("%s\n%s\n",a.c_str(),b.c_str());
    if(a==b) printf("Yes\n%s\n",a.c_str());
    else printf("No\n");
    return 0;
}



活动打卡代码 AcWing 516. 神奇的幻方

#include<cstdio>
#include<iostream>
#define LL long long
#define rint register int
using namespace std;
const int N=50*50;
int n;
int a[N][2];
int ans[50][50];
int main()
{
//  freopen("1.in","r",stdin);
    int i,j;
    cin>>n;
    a[1][0]=1;
    a[1][1]=(n+1)>>1;
    ans[a[1][0]][a[1][1]]=1;
    for(i=2;i<=n*n;i++) {
        if(a[i-1][0]==1&&a[i-1][1]<n) 
            a[i][0]=n,a[i][1]=a[i-1][1]+1;
        else if(a[i-1][0]>1&&a[i-1][1]==n) 
            a[i][0]=a[i-1][0]-1,a[i][1]=1;
        else if(a[i-1][0]==1&&a[i-1][1]==n) 
            a[i][0]=2,a[i][1]=n;
        else if(ans[a[i-1][0]-1][a[i-1][1]+1]==0) 
            a[i][0]=a[i-1][0]-1,a[i][1]=a[i-1][1]+1;
        else a[i][0]=a[i-1][0]+1,a[i][1]=a[i-1][1];
        ans[a[i][0]][a[i][1]]=i;
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) 
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 3188. manacher算法

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=2.2e7+5;

int p[N];
char a[N],c[N];

int manacher()
{
    memset(c,'\0',sizeof c);
    memset(p,0,sizeof p);
    int len=strlen(a),n=1,i,mid,r;
    c[0]='~',c[1]='|';
    for(i=0;i<len;i++) 
        c[++n]=a[i],c[++n]='|';

    for(i=1,mid=0,r=0;i<=n;i++) {
        p[i]=min(p[mid*2-i],r-i+1);
        while(c[i-p[i]]==c[i+p[i]]) p[i]++;
        if(i+p[i]-1>r) r=i+p[i]-1,mid=i; 
    }
    int ans=0;
    for(i=1;i<=n;i++)
        ans=max(ans,p[i]-1);
    return ans;
}

int main()
{
//  freopen("1.in","r",stdin);
    scanf("%s",a);
    printf("%d\n",manacher());
    return 0;
}


活动打卡代码 AcWing 3189. Lomsat gelral

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=2e5+5;

int one[N],idx;
int Next[N],ver[N];
void AddEdge(int a,int b)
{
    Next[++idx]=one[a];
    one[a]=idx;
    ver[idx]=b; 
}

int siz[N],son[N];

void dfs1(int x,int fa)
{
    int i,y;
    siz[x]=1;
    for(i=one[x];i;i=Next[i]) {
        y=ver[i];
        if(y==fa) continue;
        dfs1(y,x);
        if(siz[y]>siz[son[x]]) son[x]=y;
        siz[x]+=siz[y];
    }
}

int cnt[N],col[N],maxc;
LL sum;

void count(int x,int fa,int val,int ban)
{
    cnt[col[x]]+=val;
    if(cnt[col[x]]>maxc) maxc=cnt[col[x]],sum=0;
    if(cnt[col[x]]==maxc) sum+=col[x];

    int i,y;
    for(i=one[x];i;i=Next[i]) {
        y=ver[i];
        if(y==fa||y==ban) continue;
        count(y,x,val,ban);
    }
}
LL f[N];

void dfs2(int x,int fa,bool keep)
{
    int i,y;
    for(i=one[x];i;i=Next[i]) {
        y=ver[i];
        if(y==fa||y==son[x]) continue;
        dfs2(y,x,false);
    }
    if(son[x]) dfs2(son[x],x,true);
    count(x,fa,1,son[x]);
    f[x]=sum;
    if(!keep) count(x,fa,-1,0),maxc=sum=0;
}

int n;

int main()
{
//  freopen("1.in","r",stdin);
    int i;
    int x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&col[i]);
    for(i=1;i<=n-1;i++) {
        scanf("%d%d",&x,&y);
        AddEdge(x,y),AddEdge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,false);
    for(i=1;i<=n;i++) 
        printf("%lld ",f[i]);
    return 0;
}


活动打卡代码 AcWing 3125. 扩展BSGS

exbsgs.

#include<cmath>
#include<cstdio>
#include<iostream>
#include<unordered_map>

using namespace std;
typedef long long LL;

const LL INF=0x3f3f3f3f3f3f3f3f;

LL exgcd(LL a,LL b,LL& x,LL& y)
{
    if(b==0) {
        x=1,y=0;
        return a;
    }
    LL z=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return z;
}

LL gcd(LL a,LL b) 
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

LL inv(LL a,LL p) // 求 a 在 模p 意义下的逆元,保证 a,p 互质。 
{
    LL x,y;
    exgcd(a,p,x,y);
    x=(x%p+p)%p; // 最小正整数解。 
    return x;
}

LL bsgs(LL a,LL b,LL p)
{
    if(1%p==b%p) return 0;
    unordered_map<LL,LL> mp;
    LL k=sqrt(p)+1,ak=1;
    for(LL i=0,j=b%p;i<k;i++,j=j*a%p) 
        mp[j]=i;
    for(LL i=0;i<k;i++) ak=ak*a%p;
    for(LL i=1,j=ak;i<=k;i++,j=j*ak%p)
        if(mp.count(j)) return i*k-mp[j];
    return -INF;
}

LL exbsgs(LL a,LL b,LL p)
{
    b=(b%p+p)%p;
    if(1%p==b%p) return 0;
    LL d=gcd(a,p);
    if(d==1) return bsgs(a,b,p);
    else if(b%d) return -INF;
    else return exbsgs(a%(p/d),b/d*inv(a/d,p/d)%(p/d),p/d)+1;
}

int main()
{
    LL a,p,b,ans;
    while(cin>>a>>p>>b,a||p||b) {
        ans=exbsgs(a,b,p);
        if(ans<0) puts("No Solution");
        else printf("%lld\n",ans);
    }
    return 0;
}



活动打卡代码 AcWing 1290. 越狱

#include<iostream>

using namespace std;
typedef long long LL;

const LL MOD=100003;

LL n,m;
LL power(LL x,LL k,LL MOD)
{
    LL res=1; x%=MOD;
    while(k) {
        if(k&1) res=res*x%MOD;
        x=x*x%MOD; k>>=1;
    }
    return res%MOD;
}

int main()
{
//  freopen("1.in","r",stdin);
    cin>>m>>n;
    cout<<(power(m,n,MOD)-power(m-1,n-1,MOD)*m%MOD+MOD)%MOD<<endl;
    return 0;
}



活动打卡代码 AcWing 1116. 马走日

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=1e3+5;
const int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};

int cnt;
LL ans;
bool vis[N][N];
int T,n,m;

void dfs(int x,int y)
{
    vis[x][y]=true;
    cnt++;
    if(cnt==n*m) ans++;
    for(int i=0;i<8;i++) {
        int u=x+dx[i],v=y+dy[i];
        if(u>=0 && u<n && v>=0 && v<m && !vis[u][v]) 
            dfs(u,v);
    }
    cnt--;
    vis[x][y]=false;
}

int main()
{
//  freopen("1.in","r",stdin);
    int x,y;
    cin>>T;
    while(T--) {
        memset(vis,0,sizeof vis);
        ans=cnt=0;
        cin>>n>>m>>x>>y;
        dfs(x,y);
        cout<<ans<<endl;
    }
    return 0;
}