[数据结构与算法]4/3 江苏省赛补题+思维题+逆元+遍历树

J. Anti-merge

题意增加了思维的难度。
虽然看着像之前做的二分图，但本质上就是个染色问题，stl容器的使用更易处理这个问题。
思维难点在于:我只需要一种类型的标记就可防止相邻相同类型的格子避免合并。
ans[0]记录每轮最少需要的染色次数

#include <bits/stdc++.h>

using namespace std;
const int inf=0x3f3f3f3f;
const int N=505;
int n,m,a[N][N],types;
int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
vector<pair<int,int> >ans[5];
int color[N][N];
bool check(int i,int j)
{
    int k1=0,k2=0;
    if(i-1>=1&&a[i-1][j]==a[i][j]) k1=1;
    if(j-1>=1&&a[i][j-1]==a[i][j]) k2=1;
    if(k1||k2) return 1;
    return 0;
}
void dfs(int x,int y,int col)
{
    color[x][y]=col;
    ans[col].push_back({x,y});
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(a[nx][ny]==a[x][y]&&nx>=1&&nx<=n&&ny>=1&&ny<=m)
        {
            if(!color[nx][ny])
                dfs(nx,ny,3-col);
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(check(i,j)){
                types=1;
                break;
            }
        }
        if(types) break;
    }
    if(!types)
    {
        printf("0 0");return 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ans[1].clear();ans[2].clear();
            if(!color[i][j])
                dfs(i,j,1);
            if(ans[1].size()<ans[2].size())
            {
                for(int g=0;g<ans[1].size();g++)
                    ans[0].push_back(ans[1][g]);
            }
            else
            {
                for(int k=0;k<ans[2].size();k++)
                    ans[0].push_back(ans[2][k]);
            }
        }
    }
    cout<<types<<" "<<ans[0].size()<<endl;
    for(int i=0;i<ans[0].size();i++)
        cout<<ans[0][i].first<<" "<<ans[0][i].second<<" "<<1<<endl;
    return 0;
}

抓球

一道逆元题,这类题做的很少，记录一下

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=1e6+5;
int fac[N],t,n,m,k,q;;
int fastpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a) //求逆元
{
    return fastpow(a,mod-2)%mod;
}
int C(int n,int m)  //C(n,m)
{
    return ((fac[n]*getinv(fac[m])%mod)*(getinv(fac[n-m])%mod))%mod;
}
signed main(){
    //freopen("in.txt","r",stdin);
    fac[0]=1;
    for(int i=1;i<=N;i++)
        fac[i]=fac[i-1]*i%mod;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k>>q;
        if(k>n)
        {
            cout<<0<<endl;
            continue;
        }
        int zi=fastpow(C(n,k),q)%mod,mu=fastpow(C(m+n,k),q)%mod;
        int ans=zi*getinv(mu)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

大数乘法

根据y进行拆分，eg：x的699可拆成 x的9次幂 * x的90次幂 * x的600次幂
可用一个数字分别记录,1,10,1000次幂等等

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int t,x,p,f[N];
char y[N];
int fastpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>x>>(y+1)>>p;
        f[0]=1;f[1]=x;
        for(int i=2;i<=N;i++)
            f[i]=fastpow(f[i-1],10)%p;
        int len=strlen(y+1);
        int ans=0,tmp,g=1,sum=1;
        for(int i=len;i>=1;i--)
        {
            tmp=y[i]-'0';
            ans=fastpow(f[g],tmp);ans%=p;
            sum*=ans;sum%=p;
            g++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

逆元

逆元作用
模意义下的除法在大多数时候都不适用。当题目中要求对答案取模，但我们又不得不使用一般的除法的时候，就需要用逆元的乘法来代替除法。a / b = a * b-1 ≡ a * inv[b] (mod m)
求逆元:

int getinv(int a) //求逆元
{
    return fastpow(a,mod-2)%mod;
}

求C(n,m):

int C(int n,int m)  //C(n,m)
{
    return ((fac[n]*getinv(fac[m])%mod)*(getinv(fac[n-m])%mod))%mod;
}

全排列

int main() {
	string str;  //字符串的全排列
	cin>>str;
	sort(str.begin(),str.end());
	do{
		cout<<str<<endl;
	}while(next_permutation(str.begin(),str.end()));
	return 0;
}

gk的树
统计所有大于k的度数和，再遍历整棵树，依次减去重复记得度数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,k,head[N],cnt,ans,du[N];
struct node
{
    int to,nxt;
}e[N];
void add(int from,int to)
{
    e[++cnt].to=to;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)
            continue;
        dfs(v,u);
        if(du[v]>k&&du[u]>k)
        {
            du[u]--;du[v]--;
            ans--;
        }
    }
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cnt=0;ans=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            head[i]=du[i]=0;
        for(int i=1;i<=n-1;i++)
        {
            int u,v;cin>>u>>v;
            add(u,v);add(v,u);
            du[u]++;du[v]++;
        }
        for(int i=1;i<=n;i++)
            if(du[i]>k)
            ans+=du[i]-k;
        dfs(1,0);
        cout<<ans<<endl;
        for(int i=1;i<=cnt;i++)
        {
            e[i].to=e[i].nxt=0;
        }
    }
    return 0;
}