「基本算法」例题

作者: 云中翻月 | 来源:发表于2019-03-22 22:24 被阅读0次

0x00「基本算法」例题

0101 a^b
快速幂模板，注意模数p=1的情况
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
ll a,b,p;
ll ksm(ll a,ll b,ll p){
    ll ans=1%p;//如果b=0 p=1,直接写ans=1就错了 
    while(b){
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("a^b.in","r",stdin);
    cin>>a>>b>>p;
    cout<<ksm(a,b,p);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0102 64位整数乘法
由于c++没有类型可以保存128位数，所以采用模仿快速幂的形式来求解。
具体地说，就是将b拆分二进制，然后维护位权a（每多一位都乘2），当b的对应位为1时，累加答案即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
ll a,b,p;
ll work(ll a,ll b,ll p){
    ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%p;
        a=(a*2)%p;
        b>>=1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("64位整数乘法.in","r",stdin);
    cin>>a>>b>>p;
    cout<<work(a,b,p);

    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1995 Raising Modulo Numbers
还是快速幂模板题，不再赘述

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=45000+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
ll t,m,h,a,b;
ll solve(ll a,ll b,ll m){
    ll ans=1%m;
    while(b){
        if(b&1) ans=(ans*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Raising Modulo Numbers.in","r",stdin);
    cin>>t;
    while(t--){
        cin>>m>>h;
        ll ans=0;
        while(h--){
            cin>>a>>b;
            ans=(ans+solve(a,b,m))%m;
        }
        cout<<ans<<endl;
    }

    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0103 最短Hamilton路径
数据量很小，采用状压dp。
状态定义：d[i,j]表示目前在j，已经访问过的集合为i（i是一个二进制数，若i的第k位为1，表示第k个点已经访问过）时的最小代价。
状态转移方程： $d[i,j]=min\left \{d[i\oplus(1<<j),k]+weight(k,j)\right\},\;其中\;(i >>j) \&1 且 (i\oplus(1<<j)>>k)\&1$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=20+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,a[maxn][maxn],d[(1<<20)+5][maxn];
void solve() {
    d[1][0]=0;
    for(int i=1; i<=(1<<n)-1; i++) {
        for(int j=0; j<=n-1; j++) {
            if(i&(1<<j)) {
                for(int k=0; k<=n-1; k++) {
                    if(j!=k&&((1<<k)&i)){
                        d[i][j]=min(d[i][j],d[i^(1<<j)][k]+a[k][j]);
                    }
                }
            }
        }
    }
    cout<<d[(1<<n)-1][n-1];
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("最短Hamilton路径.in","r",stdin);
    memset(d,INF,sizeof(d));
    cin>>n;
    for(int i=0; i<=n-1; i++) {
        for(int j=0; j<=n-1; j++) {
            cin>>a[i][j];
        }
    }
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

PS：若要求哈密顿回路，理论上只要将

d[1][0]=0;

和

cout<<d[(1<<n)-1][n-1];

改成

d[0][0]=0;

和

cout<<d[(1<<n)-1][0];

即可。
0201 费解的开关
只要固定第一行，剩下的所有操作必然唯一。
因此只要枚举第一行的点击状态，然后判断是否能够让所有所有灯都亮起即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=5+5;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0,0};
const int dy[]={0,0,1,-1,0};
int n,b[maxn][maxn];
char a[maxn][maxn];
bool check(int x,int y){
    if(x<0||x>4||y<0||y>4) return false;
    return true;
}
void click(int x,int y){
    for(int i=0;i<=4;i++){
        int newx=x+dx[i];
        int newy=y+dy[i];
        if(check(newx,newy)){
            b[newx][newy]^=1;
        }
    }
}
void solve(){
    int ans=INF;
    for(int i=0;i<=(1<<5)-1;i++){
        int cnt=0;
        for(int j=0;j<=4;j++){
            if(i&(1<<j)){
                cnt++;
                click(0,j);
            }
        }
        for(int j=0;j<=3;j++){
            for(int k=0;k<=4;k++){
                if(!b[j][k]){
                    cnt++;
                    click(j+1,k);
                }
            }
        }
        bool flag=true;
        for(int j=0;j<=4;j++){
            for(int k=0;k<=4;k++){
                if(!b[j][k]){
                    flag=false;
                }
            }
        }
        if(flag){
            ans=min(ans,cnt);
        }
        for(int j=0;j<=4;j++){
            for(int k=0;k<=4;k++){
                b[j][k]=(int)(a[j][k]-'0');
            }
        }
    }
    if(ans==INF||ans>6){
        cout<<-1<<endl;
    }
    else{
        cout<<ans<<endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("费解的开关.in","r",stdin);
    cin>>n;
    while(n--){
        for(int i=0;i<=4;i++){
            for(int j=0;j<=4;j++){
                cin>>a[i][j];
            }
        }
        for(int i=0;i<=4;i++){
            for(int j=0;j<=4;j++){
                b[i][j]=(int)(a[i][j]-'0');
            }
        }
        solve();
    }

    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0301 递归实现指数型枚举
每个数字都有两种选择，直接dfs即可。
代码如下

/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<string>
using namespace std;
typedef long long ll;
const int maxn=16+5;
const int INF=0x3f3f3f3f;
int n;
int vis[maxn];
int a[maxn];
void dfs(int x,int cnt) {
    if(x==n+1) {
        for(int i=0; i<cnt; i++) {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    dfs(x+1,cnt);
    a[cnt]=x;
    dfs(x+1,cnt+1);
    a[cnt]=0;

}
int main() {
    ios::sync_with_stdio(false);
    //freopen("递归实现指数型枚举.in","r",stdin);
    cin>>n;
    dfs(1,0);

    return 0;
}

0302 递归／非递归实现组合型枚举
由于要选出恰好m个，所以可以有两个剪枝。
1 如果已经选择超过m个，剪枝。
2 如果剩下的全部选上仍然不到m个，剪枝。
PS：这种dfs的方法顺便满足了字典序。
代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=37+5;
const int INF=0x3f3f3f3f;
int n,m;
vector<int>ve;
void dfs(int x){
    if(ve.size()>m||n+1-x<m-ve.size()) return; //剪枝1和剪枝2 
    if(x==n+1){
        for(int i=0;i<ve.size();i++){
            cout<<ve[i]<<" ";
        }
        cout<<endl;
        return;
    }
    ve.push_back(x);
    dfs(x+1);
    ve.pop_back();
    dfs(x+1);
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("递归／非递归实现组合型枚举.in","r",stdin);
    cin>>n>>m;
    dfs(1);
    return 0;
}

0303 递归实现排列型枚举
法一：使用next_permutation(a+1,a+n+1)这个函数即可。
法二：在dfs中额外使用一个order数组记录顺序。
两种方法代码如下

/*

*/
#define method_2
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=10+5;
const int INF=0x3f3f3f3f;
int n,a[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("递归实现排列型枚举.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    do{
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }while(next_permutation(a+1,a+n+1));
    
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=10+5;
const int INF=0x3f3f3f3f;
int n,order[maxn],vis[maxn];
void dfs(int x){
    if(x==n+1){
        for(int i=1;i<=n;i++) cout<<order[i]<<" ";
        cout<<endl;
        return; 
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        vis[i]=1;
        order[x]=i;
        dfs(x+1);
        vis[i]=0;
        order[x]=0;//由于有vis数组的限制 所以这一行可以省略 
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("递归实现排列型枚举.in","r",stdin);
    cin>>n;
    dfs(1);
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

POJ1958 Strange Towers of Hanoi
汉诺4塔问题，可以借助3塔问题考虑，首先递推出汉诺3塔的步数d[i]，然后i层汉诺4塔的最少步数f[i]是
$f[i]=\min_{1\leq i <n} \left\{ f[j]*2+d[i-j] \right\}$
该式可以理解为先移动j个盘片到一个中转塔上，然后再在三塔情况下移动i-j个盘片到目标塔上，最后再将j个盘片移动到目标塔上。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=12+5;
const int INF=0x3f3f3f3f;
ll d[maxn],f[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("Strange Towers of Hanoi.in","r",stdin);
    memset(f,INF,sizeof(f));
    d[1]=f[1]=1;
    for(int i=2;i<=12;i++){
        d[i]=d[i-1]*2+1;
    }
    cout<<f[1]<<endl;
    for(int i=2;i<=12;i++){
        for(int j=1;j<i;j++){
            f[i]=min(f[i],2*f[i-j]+d[j]);
        }
        cout<<f[i]<<endl;
    }
    
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1845 Sumdiv
对A分解质因数，即 $A=p_{1}^{e_{1}}*p_{2}^{e_{2}}*...*p_{k}^{e_{k}}$ ，则其约数的和就是
$(1+p_{1}+p_{1}^{2}+p_{1}^{3}+...+p_{1}^{e_{1}})*(1+p_{2}+p_{2}^{2}+p_{2}^{3}+...+p_{2}^{e_{2}})*...*(1+p_{k}+p_{k}^{2}+p_{k}^{3}+...+p_{k}^{e_{k}})$
答案就是
$(1+p_{1}+p_{1}^{2}+p_{1}^{3}+...+p_{1}^{B*e_{1}})*(1+p_{2}+p_{2}^{2}+p_{2}^{3}+...+p_{2}^{B*e_{2}})*...*(1+p_{k}+p_{k}^{2}+p_{k}^{3}+...+p_{k}^{B*e_{k}})$
考虑计算
$1+p_{i}+p_{i}^{2}+p_{i}^{3}+...+p_{i}^{B*e_{i}}$
即计算
$sum(p,c)=1+p+p^{2}+p^{3}+...+p^{c}$
作如下变形
$1+p+p^{2}+p^{3}+...+p^{c}=(1+p+...+p^{\frac{c-1}{2}})+(p^{\frac{c+1}{2}}+...+p^{c})$
对后一半的项提取公因式
$(1+p+...+p^{\frac{c-1}{2}})+(p^{\frac{c+1}{2}}+...+p^{c})=(1+p+...+p^{\frac{c-1}{2}})+p^{\frac{c+1}{2}}*(1+p+...+p^{\frac{c-1}{2}})$
即
$(1+p^{\frac{c+1}{2}})*sum(p,\frac{c-1}{2})$
因此可以配合快速幂进行分治计算。
注意要对c分奇偶讨论。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=10000+5;
const int INF=0x3f3f3f3f;
const int mod=9901;
ll a,b;
ll cnt=0,prime[maxn],notprime[maxn];
void pre() {
    prime[++cnt]=2;
    for(int i=3; i<=10003; i+=2) {
        if(notprime[i]) continue;
        prime[++cnt]=i;
        for(int j=i*2; i*j<=10003; j+=i) {
            notprime[i*j]=1;
        }
    }
}
ll e[maxn];
vector<pair<int, int> > vpi;
void fj(ll x) {
    int qwq = 0;
    for(int i = 1; i <= cnt; ++i) {
        qwq = 0;
        while(x % prime[i] == 0)
            x /= prime[i], ++qwq;
        if(qwq) vpi.push_back(make_pair(prime[i], qwq));
    }
    if(x != 1) vpi.push_back(make_pair(x, 1));
}
void pre1() {
    for(int i=1; i<=cnt; i++) {
        while(a%prime[i]==0){
            a/=prime[i];
            e[prime[i]]++;
        }
    }
    if(a!=1) prime[a]++; 
}
ll ksm(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll cal(ll p,ll c){ //计算1+pi^1+pi^2+...+pi^Bei 
    if(!c) return 1;
    if(!p) return 0;
    if(c&1){
        return (((1+ksm(p,(c+1)/2))%mod)*cal(p,(c-1)/2))%mod;
    }
    else{
        return (ksm(p,c)+(cal(p,(c-1)/2)*(1+ksm(p,c/2)))%mod)%mod;
    }
}
void work(){
    ll ans=1;
    /*
    for(int i=1;i<=cnt;i++){
        if(e[prime[i]]!=0) ans=(ans*(cal(prime[i],b*e[prime[i]]))%mod)%mod;
        //if(e[prime[i]]!=0){
        //  cout<<prime[i]<<" "<<e[prime[i]]<<" "<<cal(prime[i],b*e[prime[i]])<<endl;
        //}
    }
    */
    for(int i = 0; i < vpi.size(); ++i) {
        ans = (ans * cal(vpi[i].first, b * vpi[i].second)) % mod;
    }
    cout<<ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Sumdiv.in","r",stdin);
//  cout<<ksm(2,2)<<endl;
    cin>>a>>b;
    pre();//生成素数表
//  pre1(); //分解质因数
    fj(a);
    work();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0304 IncDec Sequence
由于存在大量区间操作，所以用差分的方法转化为单点操作。假设差分序列为b，最终目标就是 $b_{2},b_{3}...b_{n}$ 为0。
对序列的操作有四种。
1 选择 $a_{1}$ 和 $a_{n}$ ，相当于选择了 $b_{1}$ 和 $b_{n+1}$ ，没有意义。
2 选择 $a_{1}$ 和 $a_{i},i\neq n$ ，相当于选择了 $b_{1}$ 和 $b_{i+1}$ ，每次让b序列中的一个数的绝对值变化1。
3 选择 $a_{i},i\neq n$ 和 $a_{n}$ ，相当于选择了 $b_{i}$ 和 $b_{n+1}$ ，每次让b序列中的一个数的绝对值变化1。
4 选择 $a_{i},i\neq n$ 和 $a_{j},j\neq n$ ，相当于选择了 $b_{i}$ 和 $b_{j+1}$ ，每次让b序列中的一个数的绝对值变化2。
因此，首先应该尽量多的使用操作4，剩下的在操作2和操作3中每次随便选即可。
设b序列中除了 $b_{1}$ ，正数和为p，负数和为q，则总共进行 $min(p,q)$ 次操作4，然后操作2可以进行 $0到|p-q|$ 次，总共进行 $max(p,q)$ 次操作。所以最后会产生 $|p-q|+1$ 种不同的 $b_{1}$ 的值，也就是最后a序列可能会有 $|p-q|+1$ 种不同的情况。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
ll n,a[maxn],b[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("IncDec Sequence.in","r",stdin);
    cin>>n;
//  a[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>=2) b[i]=a[i]-a[i-1];
    }
    ll p=0,q=0;
    for(int i=2;i<=n;i++){
        if(b[i]>0) p+=b[i];
        else q-=b[i];
    }
    cout<<max(p,q)<<endl<<abs(p-q)+1;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ2018 Best Cow Fences
实数域上二分答案，每次将所有数字减去二分的答案，然后从左往右扫描一遍，判断是否存在长度大于等于L的非负子段即可。
具体判断是否存在长度大于等于L的非负子段时，首先转化为前缀和相减的形式。维护一个minval的变量表示max(0,i-L)的最小sum值即可，具体详见代码。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-5;
int n,L;
double a[maxn],b[maxn],s[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("Best Cow Fences.in","r",stdin);
    cin>>n>>L;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    double l=0.0,r=(double)(INF);
    while(l+eps<r){
        double mid=(l+r)/2;
        for(int i=1;i<=n;i++){
            b[i]=a[i]-mid;
        }
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+b[i];
        }
        double minval=double(INF);
        double ans=double(-INF);
        for(int i=L;i<=n;i++){
            minval=min(minval,s[i-L]);
            ans=max(ans,s[i]-minval);
        }
        if(ans>=0){
            l=mid;
        }
        else r=mid;
    }
    cout<<(int)(r*1000);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0501 货仓选址
考虑放在某一段，则它在向中位数移动调整的过程中，总距离始终在减小，在中位数处达到最小。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
ll n,a[maxn]; 
int main() {
    ios::sync_with_stdio(false);
    //freopen("货仓选址.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    ll ans=0;
    if(n&1){
        for(int i=1;i<=n;i++){
            ans+=abs(a[(n+1)/2]-a[i]);
        }
    }
    else{
        for(int i=1;i<=n;i++){
            ans+=abs(a[n/2]-a[i]);
        }
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0502 七夕祭
横竖方向互相独立，所以分开考虑。
然后环形传递有个结论，必然存在两个点之间没有传递，这个可以通过反证法证明。
然后写出前缀和的答案，枚举断开处，发现当断开处是前缀和的中位数时，就有了最优情况。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
ll n,m,t,r[maxn],c[maxn],sc[maxn],sr[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("七夕祭.in","r",stdin);
    cin>>n>>m>>t;
    ll x,y,flag;
    if(t%n&&t%m){
        cout<<"impossible";
        return 0;
    }
    else if(t%n==0&&t%m){
        cout<<"row ";
        flag=1;
    }
    else if(t%n&&t%m==0){
        cout<<"column ";
        flag=2;
    }
    else{
        cout<<"both ";
        flag=3;
    }
    ll midr=t/n,midc=t/m;
//  cout<<midr<<" "<<midc;
    while(t--){
        cin>>x>>y;
        r[x]++;
        c[y]++;
    }
    for(int i=1;i<=n;i++){
        r[i]-=midr;
        sr[i]=sr[i-1]+r[i];
    }
    for(int i=1;i<=m;i++){
        c[i]-=midc;
        sc[i]=sc[i-1]+c[i];
    }
    sort(sr+1,sr+n+1);
    sort(sc+1,sc+m+1);
    ll ansr=0,ansc=0; 
    for(int i=1;i<=n;i++){
        ansr+=abs(sr[(n+1)/2]-sr[i]);
    } 
    for(int i=1;i<=m;i++){
        ansc+=abs(sc[(m+1)/2]-sc[i]);
    } 
    if(flag==1) cout<<ansr;
    else if(flag==2) cout<<ansc;
    else cout<<ansr+ansc;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ2299 Ultra-QuickSort
每次交换都会让逆序对减少一，最终序列的逆序对数为0。因此题目转化为求逆序对问题，归并或者树状数组均可。
这里提供了两种做法（method_2是树状数组的做法，由于数字的范围较大，所以采用了离散化）
代码如下

/*
*/
#define method_2
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
ll n,ans,a[maxn],b[maxn];
void merge(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int j=l,k=mid+1;
    for(int i=l;i<=r;i++){
        if(k>r||(j<=mid&&a[j]<=a[k])) b[i]=a[j++];
        else{
            b[i]=a[k++];
            ans+=mid-j+1;
        }
    }
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Ultra-QuickSort.in","r",stdin);
    while(cin>>n&&n!=0){
        ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        merge(1,n);
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
ll n,ans,a[maxn],b[maxn],cnt,c[maxn];
int lowbit(int x){
    return x&-x;
    //return x&(~x+1)
} 
void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=v;
    }
}
int sum(int x){
    int sum=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        sum+=c[i];
    }
    return sum;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Ultra-QuickSort.in","r",stdin);
    while(cin>>n&&n!=0){
        ans=cnt=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            b[++cnt]=a[i];
        }
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
        //  cout<<a[i]<<" ";
        }
    //  cout<<endl;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            add(a[i],1);
            ans+=i-sum(a[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

0503 奇数码问题
首先存在结论，两个局面互相可达等价于两个局面转化成一维序列的逆序对奇偶性相同。
证明：对于空格在一行内移动的情况，逆序对不变。对于空格在上下移动的情况，每次移动会和交换到n-1个数的前面，所以由于n是奇数，所以n-1是偶数，所以逆序对的改变数也是偶数，因此奇偶性始终不变。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=500*500+5;
const int INF=0x3f3f3f3f;
ll n,a[maxn],b[maxn];
ll ans1=0,ans2=0;
void merge(int l,int r,int f) {
    if(l>=r) return;
    int mid=(l+r)>>1;
    merge(l,mid,f);
    merge(mid+1,r,f);
    int j=l,k=mid+1;
    for(int i=l; i<=r; i++) {
        if(k>r||(j<=mid&&a[j]<=a[k])) b[i]=a[j++];
        else {
            b[i]=a[k++];
            if(f==1) ans1+=mid-j+1;
            else ans2+=mid-j+1;
        }
    }
    for(int i=l; i<=r; i++) {
        a[i]=b[i];
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("奇数码问题.in","r",stdin);
    while(cin>>n) {
        
        ans1=ans2=0;
        ll cnt=1,top=0;
        ll x;
    //  if(n==1) cin>>x>>x;
        while(cnt<=n*n) {
            cin>>x;
            ++cnt;
            if(x!=0) a[++top]=x;
        }
    //  for(int i=1;i<=n*n-1;i++){
    //      cout<<a[i]<<" ";
    //  }
        merge(1,n*n-1,1);
        cnt=1;
        top=0;
        while(cnt<=n*n) {
            cin>>x;
            ++cnt;
            if(x!=0) a[++top]=x;
        }
        merge(1,n*n-1,2);
        if((ans1&1)==(ans2&1)) cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

0601 Genius ACM
每一段的最优解肯定是这一段排序后最大的m个数和最小的m个数组合的结果。
因此我们采用倍增的方法不断拓展右端点即可。
注意，由于只有每次纳入新区间的部分是无序的，所以只要对这一段快排，然后采用和之前的区间进行归并的方法排序即可。
代码如下

/*

*/
#define method_2
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
const int INF=0x3f3f3f3f;
ll t,n,m,k,a[maxn],aa[maxn];
int main() {
    ios::sync_with_stdio(false);
    freopen("Genius ACM.in","r",stdin);
    cin>>t;
    while(t--) {
        cin>>n>>m>>k;
        for(int i=1; i<=n; i++) {
            cin>>a[i];
        }
        memcpy(aa,a,sizeof(a));

    }
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=510010;
int n,m;
ll T;
ll s[N],tmp[N],tmp2[N];
bool calc(int l,int rr,int r) { //l~rr有序  rr~r无序 
    int t=l,len=r-l+1;
    for(int i=rr; i<=r; i++) tmp[i]=s[i];
    sort(tmp+rr,tmp+r+1);
    if(l==rr) for(int i=l; i<=r; i++) tmp2[i]=tmp[i];
    else {
        int i=l,j=rr;
        while(i<rr && j<=r) {
            if(tmp[i]<=tmp[j]) tmp2[t++]=tmp[i++];
            else tmp2[t++]=tmp[j++];
        }
        while(i<rr) tmp2[t++]=tmp[i++];
        while(j<=r) tmp2[t++]=tmp[j++];
    }
    ll sum=0;
    for(int i=l; i<=min(l+len/2-1,l+m-1); i++) {
        sum+=(tmp2[i]-tmp2[r-i+l])*(tmp2[i]-tmp2[r-i+l]);
    }
    if(sum<=T) {
        for(int i=l; i<=r; i++) tmp[i]=tmp2[i];
        return 1;
    } else return 0;
}
int main() {
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    //freopen("Genius ACM.in","r",stdin);
    int ti;
    scanf("%d",&ti);
    while(ti--) {
        scanf("%d%d%lld",&n,&m,&T);
        for(int i=1; i<=n; i++) scanf("%lld",&s[i]);
        memset(tmp,0,sizeof(tmp));
        memset(tmp2,0,sizeof(tmp2));
        int p=1,l=1,r=1,ans=1;
        tmp[1]=s[1];
        while(r<n) {
            if(!p) {
                ans++;
                p=1;
                r++;
                l=r;
                tmp[l]=s[l];
                continue;
            }
            if(p) {
                if(r+p<=n && calc(l,r+1,r+p)) { 
                //这里一定要先判断再运算，要不然会先执行运算然后炸掉
                    r+=p,p*=2;
                } else p/=2;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

#endif
#ifdef method_3
/*

*/

#endif

POJ3614 Sunscreen
按照每头牛的minspf降序排序，然后选择对应可以使用的防晒霜种spf值最大的防晒霜即可，这样可以让“浪费”尽量小。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=2500+5;
const int INF=0x3f3f3f3f;
int c,l;
struct node{
    int x,y;
}p[maxn],q[maxn]; 
int ans=0;
bool operator<(const node &a,const node &b){
    return a.x>b.x;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Sunscreen.in","r",stdin);
    cin>>c>>l;
    for(int i=1;i<=c;i++){
        cin>>p[i].x>>p[i].y; 
    }
    for(int i=1;i<=l;i++){
        cin>>q[i].x>>q[i].y;
    }
    sort(p+1,p+c+1);
//  for(int i=1;i<=c;i++){
//      cout<<p[i].x<<endl;
//  }
    for(int i=1;i<=c;i++){
        int temp=-1,id=-1;
        for(int j=1;j<=l;j++){
            if(q[j].y>0&&(p[i].x<=q[j].x)&&(p[i].y>=q[j].x)){
                if(q[j].x>temp){
                    temp=q[j].x;
                    id=j;
                }
            }
        }
        if(temp!=-1){
            ans++;
            q[id].y--;
        }
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1328 Radar Installation
将每个圆在x轴上的截距作为区间，那么就转化为了区间覆盖问题，按照区间的左端点升序排序，依次考虑即可。
0701 国王游戏
贪心排序，按照每个大臣左右手数字乘积升序排序即可。
证明，假设第i大臣左右手上的数字分别为A[i]和B[i]，国王手中的数字是A[0]和B[0]。
则i大臣的获利是 $\frac{\prod_{j=0}^{i-1}A[i]}{B[i]}$
i+1大臣的获利是 $\frac{\prod_{j=0}^{i}A[i]}{B[i+1]}$
此时 $A[i]*B[i]>A[i+1]*B[i+1]$
若交换后，获利产生变化的只有这两个大臣。
其中i大臣的获利是 $\frac{A[i+1]*\prod_{j=0}^{i-1}A[i]}{B[i]}$
i+1大臣的获利是 $\frac{\prod_{j=0}^{i-1}A[i]}{B[i+1]}$
提取公因式 $\prod_{j=0}^{i-1}A[i]$
我们要比较的是 $max(\frac{1}{B[i]},\frac{A[i]}{B[i+1]})$ 和 $max(\frac{1}{B[i+1]},\frac{A[i+1]}{B[i]})$ 的大小。
两边同时乘以 $B[i]*B[i+1]$
变为比较 $max(B[i+1],A[i]*B[i])$ 和 $max(B[i],A[i+1]*B[i+1])$
因为大臣手上的数字都是正整数，所以 $A[i]*B[i] \geq B[i]$ ，由于排序，所以 $A[i]*B[i]\leq A[i+1]B[i+1]$
所以交换前更优，证毕。
代码如下（由于数字过大，需要用到高精度）：

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Wint:vector<int> {
    Wint(const int &n=0) {
        push_back(n);
        check();
    }
    Wint& check() {
        while(!empty()&&!back())pop_back();
        if(empty())return *this;
        for(int i=1; i!=size(); ++i) {
            (*this)[i]+=(*this)[i-1]/10;
            (*this)[i-1]%=10;
        }
        while(back()>=10) {
            push_back(back()/10);
            (*this)[size()-2]%=10;
        }
        return *this;
    }
};
ostream& operator<<(ostream &os,const Wint &w) {
    for(int i=w.size()-1; i!=-1; --i)os<<w[i];
    return w.empty()?os<<0:os;
}
bool operator<(const Wint &a,const Wint &b) {
    if(a.size()!=b.size())return a.size()<b.size();
    for(int i=a.size()-1; i!=-1; --i)
        if(a[i]!=b[i])return a[i]<b[i];
    return 0;
}
Wint& operator*=(Wint &w,const int &n) {
    for(int i=0; i!=w.size(); ++i)w[i]*=n;
    return w.check();
}
Wint operator/(Wint w,const int &n) {
    for(int i=w.size()-1,mod=0; i!=-1; --i) {
        w[i]+=mod*10;
        mod=w[i]%n;
        w[i]/=n;
    }
    return w.check();
}
struct People {
    int a,b;
};
bool operator<(const People &m,const People &n) {
    if(m.a*m.b!=n.a*n.b)return m.a*m.b<n.a*n.b;
    if(m.a!=n.a)return m.a<n.a;
    return 0;
}
int main() {
    //freopen("国王游戏.in","r",stdin);
    vector<People> v(1);
    int n;
    Wint s=1,ans=0;
    cin>>n>>v.back().a>>v.back().b;
    while(n--) {
        v.push_back(v.front());
        cin>>v.back().a>>v.back().b;
    }
    sort(v.begin()+1,v.end());
    for(int i=1; i!=v.size(); ++i) {
        s*=v[i-1].a;
        ans=max(ans,s/v[i].b);
    }
    cout<<ans;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ2054 Color a Tree
存在贪心性质：权值最大的点（除根节点）一定会在其父节点被染色后立即被染色。
由于这一对连续进行的染色关系，所以我们可以把两个点合并起来，权值等效为两点权值和的平均值，可以证明，这样做不会影响结果。
因此，我们只要不断在树上找到等效权值最大的点，然后和其父节点合并并计算代价即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
struct node {
    int c,p,t; //c：初始权值 p：父节点 t：染色时间 
    double w; //等效权值 
} num[maxn];
int ans,r,n;
int find(){
    int res;
    double maxr=0.0;
    for(int i=1;i<=n;i++){
        if(i!=r&&num[i].w>maxr){
            maxr=num[i].w;
            res=i;
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Color a Tree.in","r",stdin);
    while(cin>>n>>r&&n||r) {
        ans=0;
        for(int i=1; i<=n; i++) {
            cin>>num[i].c;
            num[i].w=num[i].c;
            ans+=num[i].c;
            num[i].t=1;
        }
        int a,b;
        for(int i=1;i<=n-1;i++){
            cin>>a>>b;
            num[b].p=a; 
        } 
        for(int i=1;i<n;i++){ //n-1条边 
            int pos=find(); //找到等效权值最大的点 
            num[pos].w=0; //之后不会find到它 
            int f=num[pos].p;
            ans+=num[pos].c*num[f].t;
            for(int j=1;j<=n;j++){ //将当前点和f合并 
                if(num[j].p==pos){
                    num[j].p=f;
                }
            }
            num[f].c+=num[pos].c;
            num[f].t+=num[pos].t;
            num[f].w=double(num[f].c)/num[f].t;
            //合并结束 
        }
        cout<<ans<<endl;
    }
    
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

「基本算法」例题

0x00「基本算法」例题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读