“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学)

Problem A 小花梨的字符串

https://acm.ecnu.edu.cn/contest/173/problem/A/

题意：对区间子字符串排列，使得满足条件，求排列最长。

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str[N];
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    cin>>str;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        cout<<(r-l+1)*(r-l+2)/2<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B 小花梨的三角形

https://acm.ecnu.edu.cn/contest/173/problem/B/

题意：统计三个顶点不完全相同的三角形个数。

题解：枚举

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
bool vis[N][N][N];
char str[N][N];
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
        scanf("%s",str[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int k=i+1;k<=n+1;k++){
                int a[4];
                a[0]=str[k][j]-'a';
                a[1]=str[i][j]-'a';
                a[2]=str[k][j+k-i]-'a';
                sort(a,a+3);
                //cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
                vis[a[0]][a[1]][a[2]]=1;
            }

        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            for(int k=j+1;k<=i&&i+k-j<=n+1;k++){
                int a[4];
                a[0]=str[i][j]-'a';
                a[1]=str[i][k]-'a';
                a[2]=str[i+k-j][k]-'a';
                sort(a,a+3);
                //cout<<i<<" "<<j<<" "<<k<<" "<<i+k-j<<endl;
                //cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
                vis[a[0]][a[1]][a[2]]=1;
            }

        }
    }
    for(int i=0;i<26;i++){
        for(int j=i;j<26;j++){
            for(int k=j;k<26;k++){
                ans+=vis[i][j][k];
            }
        }
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C 小花梨判连通

https://acm.ecnu.edu.cn/contest/173/problem/C/

题意：有K张联通图，求使得 𝑖和𝑗在这 𝑘张图中都是连通的j的个数

C++版本一

题解：直接 dfs 、BFS 或者并查集对每张图进行连通块染色， 或者并查集对每张图进行连通块染色，  两个点在 k张图中都相邻说明这两个点在 张图中都相邻说明这两个点在 张图中都相邻说明这两个点在 k张图的染色 都是一样的 
map<vector<int>,int>存下每个点在 k张图的颜色序  列出现的次数即可 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int pre[20][N];
char str;
bool vis[N];
struct node{};
vector<int>G[N];
vector<int>V[N];
map<vector<int>,int>mp;
int find(int *pre,int x){return pre[x]==x?x:pre[x]=find(pre,pre[x]);}
void dfs(int u){
    vis[u]=1;
    V[u].push_back(cnt);
    //cout<<u<<" "<<cnt<<endl;
    for(int i=0,j=G[u].size();i<j;i++){
        int v=G[u][i];
        if(!vis[v]){
            dfs(v);
        }
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=m;i++)
        for(int j=1;j<=n;j++)
            pre[i][j]=j;
    for(int i=1;i<=m;i++){
        scanf("%d",&k);
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n;j++)
            G[j].clear();
        cnt=0;
        for(int j=1;j<=k;j++){
            scanf("%d%d",&u,&v);
            int fx=find(pre[i],u);
            int fy=find(pre[i],v);
            if(fx!=fy){
                pre[i][fy]=fx;
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }
        for(int j=1;j<=n;j++){
            if(vis[j]==0)++cnt,dfs(j);
        }
    }
    for(int i=1;i<=n;i++){
        mp[V[i]]++;
    }
    for(int i=1;i<=n;i++)cout<<mp[V[i]]<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

 题解：对每一个图dfs求联通块并染色，处于同一个联通块中的点染成相同的颜色。染色之后对于图中的每一个点就有一个长度为k的颜色序列，两点在k张图中均联通即两个点的颜色序列完全相同。求每个点的颜色序列的hash值，并记录每种hash值出现了多少次。输出答案时将该点对应的hash值出现的次数输出即可。

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;
bool vis[maxn];
vector<int> e[11][maxn];
unsigned long long ans[maxn];
int c[11][maxn];
int col = 0;
map<unsigned long long, int> mp;

void dfs(int deep, int now) {
    if (vis[now]) return;
    c[deep][now] = col;
    vis[now] = true;
    for (auto p:e[deep][now]) {
        dfs(deep, p);
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    int n, k, m;
    scanf("%d %d", &n, &k);
    int u, v;
    for (int i = 0; i < k; i++) {
        cin >> m;
        for (int j = 0; j < m; j++) {
            scanf("%d %d", &u, &v);
            e[i][u].push_back(v);
            e[i][v].push_back(u);
        }
        col = 0;
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j <= n; j++) {
            if (!vis[j]) col++;
            dfs(i, j);
        }
    }
    unsigned long long hash;
    for (int i = 1; i <= n; i++) {
        hash = 0;
        for (int j = 0; j < k; j++) {
            hash = hash * mod + c[j][i];
        }
        mp[hash]++;
        ans[i] = hash;
    }
    for (int i = 1; i <= n; i++) {
        cout << mp[ans[i]] << endl;
    }
    return 0;
}

Problem D 小花梨的取石子游戏

https://acm.ecnu.edu.cn/contest/173/problem/D/

题意：按规则取石子，求第i轮必胜的人

题解：博弈，谁先拿到非1的堆，谁就是赢家。因为足够聪明，所有人必然使得自己永远占先机。

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N],b[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    flag=2*n+1;
    for(int i=2*n;i>=1;i--){
        if(a[i]!=1)
            flag=i;
        b[i]=flag;
    }
    for(int i=1;i<=n;i++){
        cout<<((min(n-1,b[i]-i))%2==0?"First":"Second")<<endl;
    }


    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E 小花梨的数组

https://acm.ecnu.edu.cn/contest/173/problem/E/

题意：

题解：线段树+tag标记

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=1000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int f[M],prime[M],pre[N];
ll tree[N<<2],tag[N<<2];
ll POW(ll a,ll b,ll c){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}

void init(){
    f[1]=1;
    prime[0]=prime[1]=1;
    for(int i=2;i<=1e6;i++){
        if(prime[i]==0){
            pre[++cnt]=i;
            f[i]=i;
        }
        for(int j=1;j<=cnt&&pre[j]*i<=1e6;j++){
            prime[i*pre[j]]=1;
            f[i*pre[j]]=pre[j];
            if(i%pre[j]==0){
                break;
            }
        }
    }
}
void pushup(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void pushdowm(int rt){
    tag[rt<<1]+=tag[rt];
    tag[rt<<1|1]+=tag[rt];
    tag[rt]=0;
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%lld",&tree[rt]);
        tag[rt]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);

}
void updata1(int l,int r,int rt,int L,int R){
    if(tree[rt]==r-l+1)
        return;
    if(L<=l&&r<=R){
        tag[rt]++;
        return;
    }
    pushdowm(rt);
    int mid=(l+r)>>1;
    if(L<=mid)updata1(l,mid,rt<<1,L,R);
    if(R>mid)updata1(mid+1,r,rt<<1|1,L,R);
    pushup(rt);
}
void updata2(int l,int r,int rt,int L,int R){
    if(tree[rt]==r-l+1)
        return;
    if(L<=l&&r<=R&&tag[rt]){
        tag[rt]--;
        return;
    }
    if(l==r){
        tree[rt]=tree[rt]/f[tree[rt]]%MOD;
        return;
    }
    pushdowm(rt);
    int mid=(l+r)>>1;
    if(L<=mid)updata2(l,mid,rt<<1,L,R);
    if(R>mid)updata2(mid+1,r,rt<<1|1,L,R);
    pushup(rt);
}
ll query(int l,int r,int rt,int L){
    if(tree[rt]==r-l+1)
        return 1;
    if(l==r){
        return tree[rt]*POW(f[tree[rt]],tag[rt],MOD)%MOD;
    }
    pushdowm(rt);
    int mid=(l+r)>>1;
    if(L<=mid)return query(l,mid,rt<<1,L);
    else return query(mid+1,r,rt<<1|1,L);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    init();
    while(~scanf("%d%d",&n,&m)){
        memset(tree,0,sizeof(tree));
        build(1,n,1);
        for(int i=1;i<=m;i++){
            scanf("%d",&k);
            if(k==1){
                scanf("%d%d",&l,&r);
                updata1(1,n,1,l,r);
            }else if(k==2){
                scanf("%d%d",&l,&r);
                updata2(1,n,1,l,r);
            }else{
                scanf("%d",&l);
                cout<<query(1,n,1,l)<<endl;
            }
        }
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F 小花梨的无向图

https://acm.ecnu.edu.cn/contest/173/problem/F/

题意：

题解：

C++版本一

Problem G 小花梨的函数

https://acm.ecnu.edu.cn/contest/173/problem/G/

题意：

题解：

C++版本一

Problem H 小花梨的矩阵

https://acm.ecnu.edu.cn/contest/173/problem/H/

题意：

题解：

C++版本一

Problem I 小花梨点外卖

https://acm.ecnu.edu.cn/contest/173/problem/I/

题意：有两种优惠，最多选择一种，使得付款最小

题解：模拟

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,a,b,c,d;
ll ans,cnt,flag,temp,sum;
int v[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
        sum+=v[i];
    }
    if(sum>=a&&sum>=c){
        ans=sum-max(b,d);
    }else if(sum>=a){
        ans=sum-b;
    }else if(sum>=c){
        ans=sum-d;
    }else{
        ans=sum;
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}