杭电多校第三场1004、1005、1007、1009

发布于 2020-07-29  0 次阅读


4.Tokitsukaze and Multiple

思路:

理解题意:将序列分成若干段,看倍速为p的有几段
记录数组a的前缀和并且对p取模,当同一个数字出现两次时,说明该段的数字之和应该是p的倍速,取模为0的情况直接为p的倍速

AC Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
// #define TDS_ACM_LOCAL
const int N=1e5 + 9;
int n, p, a[N], sum, ans;
map<int,int>mp;
void solve(){
    cin>>n>>p;
    for(int i=1; i<=n; i++) cin>>a[i];
    mp.clear();
    ans=0, sum=0, mp[0]=1;
    for(int i=1; i<=n; i++){
        sum=(sum+a[i])%p;
        if(mp[sum]){ 
            mp.clear();
            mp[0]=1, ans++, sum=0;
        }
        else    mp[sum]=1;
    }
    cout<<ans<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

9.Parentheses Matching

题目大意:

由左右括号和乘法符号组成的字符串 ()* ,其中*可以变成(、)、‘ ’,求生成的最短的平衡括号序列中的字典序最小的,左小于右边。

思路:

开一个栈存左括号,当输入右括号的且栈不为空的时候出栈,如果栈为空,则考虑最左边的号,将其转变为(
最后判断栈内是否有剩余的的元素(即为左括号),考虑最右边的
号变为)
同时考虑*的有无,判断有无解

AC Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int a[N];
char p[N], s[N];
int idxa, idxp, idxi, flag, len;
stack<int>st;
void solve(){
    cin>>s;
    idxa=idxp=flag=0;               //idxa为存*号的下标,idxp为最终答案的下标, flag为是否有解
    len=strlen(s);
    memset(a, 0, sizeof(len+2));    //
    while(!st.empty())  st.pop();   //清空栈
    for(int i=0; i<len; i++){
        if(s[i]=='*')   a[++idxa]=i, p[i]=' ';      //将*号存入a,默认*号显示为' '
        else if(s[i]=='(')  st.push(i), p[i]='(';   //左括号进栈,p记录答案
        else if(s[i]==')'){
            if(!st.empty()) st.pop();               //栈不为空(栈中有'(' ),出栈,即为完成一个括号的匹配
            else {
                if(idxp>=idxa)  {flag=1; break;}    //如果)左边无*号,无解
                else    p[a[++idxp]]='(';           //将使用的*号的位置以(的方式存入p
            }
            p[i]=')';                               //将此次的)存入答案p
        }
    }
    while(!st.empty()){                              //栈不为空(即还有多余的(为匹配完?)
        idxi=st.top(); st.pop();
        if(idxp>=idxa || a[idxa]<idxi)  {flag=1; break;}    //判断最右边是否有*号
        p[a[idxa--]]=')';                                   //相应的*号位置存入)
    }

    if(flag)    {cout<<"No solution!"<<endl;  return ;}
    for(int i=0; i<len; i++) if(p[i]!=' ')   cout<<p[i];
    cout<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

5.Little W and Contest(并查集)

题目大意:

俱乐部有n个人,其中有标号为1和2的两种人, 一个队伍至少保包含两个标号为2的人
最开始大家相互不熟悉,每天会有人相互认识,也可以通过认识的人去认识其他人(并查集)
要求队伍中的人互相不认识,求每天可以组成的队伍

思路:

第一天大家都不认识,我们可以选择2 2 1和2 2 2,求出此时的ans
后面的几天,可以将人分成三种,当天认识的u,v和其他的w,因为u和v肯定是不互相认识的,所以认识u的,认识v的,和其他的人w,很明显当有人认识后就会出现需要除去的方案,分别从u,v,w中选
也就是这四种情况

    ans-=p2[u]*p2[v]*(cnt2-p2[u]-p2[v]);    //除去的方案为2 2 2
    ans-=p2[u]*p2[v]*(cnt1-p1[u]-p1[v]);    //除去的方案为2 2 1
    ans-=p1[u]*p2[v]*(cnt2-p2[u]-p2[v]);    //除去的方案为1 2 2
    ans-=p2[u]*p1[v]*(cnt2-p2[u]-p2[v]);    //除去的方案为2 1 2

其中的p1和p2是以i为根节点的集合中的数量
操作完后记得合并u和v的集合,同时维护根节点中的数量

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
typedef long long ll;
const int mod=1e9 +7;
const int N=1e5 +9;
ll f[N], p1[N], p2[N], a;
ll n, cnt1, cnt2, u, v;
ll ans;

void work(){
    ans-=p2[u]*p2[v]*(cnt2-p2[u]-p2[v]);    //除去的方案为2 2 2
    ans-=p2[u]*p2[v]*(cnt1-p1[u]-p1[v]);    //除去的方案为2 2 1
    ans-=p1[u]*p2[v]*(cnt2-p2[u]-p2[v]);    //除去的方案为1 2 2
    ans-=p2[u]*p1[v]*(cnt2-p2[u]-p2[v]);    //除去的方案为2 1 2
    cout<<ans%mod<<endl;
}

void Union(){       
    f[u]=v;                         //将u和v所处的集合合并
    p1[v]+=p1[u], p2[v]+=p2[u];     //集合含有的人合并
}

int find(int x){
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}

void solve(){
    cin>>n;
    ans=cnt1=cnt2=0;
    for(int i=1; i<=n; i++){
        cin>>a;
        if(a==1) cnt1++, p1[i]=1, p2[i]=0;
        else    cnt2++, p2[i]=1, p1[i]=0;
        f[i]=i;
    }
    if(cnt2>=1) ans+=cnt2*(cnt2-1)*cnt1/2;       //2 2 1的情况
    if(cnt2>=2) ans+=cnt2*(cnt2-1)*(cnt2-2)/6;  //2 2 2的情况
    cout<<ans%mod<<endl;
    for(int i=1; i<n; i++){
        cin>>u>>v;
        u=find(u), v=find(v);
        work();
        Union();
    }
    return ;
}   

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

7.Tokitsukaze and Rescue(最短路、DFS)

题目大意:

一张完全图(双向边),删去k条边后,让新图的最短路的路径长度尽可能大

思路:

先用dijkstra跑出最短路,删边肯定从这里面删的,然后枚举删除的边,再用递归求子问题(删k-1条边),ans存更新的答案
对于删边,可以采取开一个二维数组记录,也可以将删除的边记录为INF,记得回溯

AC Code:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=59;
bool vis[N], lose[N][N];
int n, k, u, v, w, ans;
int mp[N][N], path[N], dis[N];

void dijkstra(){
    memset(path, 0, sizeof(path));          //存dijkstra的路径
    memset(dis, INF, sizeof(dis));          //存最短路的路径大小
    memset(vis, 0, sizeof(vis));
    dis[1]=0, path[1]=0;
    for(int i=1; i<n; i++){
        int d=INF, f=0;
        for(int i=1; i<=n; i++) if(!vis[i]&&dis[i]<d)   d=dis[i], f=i;
        vis[f]=1;
        for(int j=1; j<=n; j++){
            if(dis[f]+mp[f][j] < dis[j] && !lose[f][j]){
                dis[j]=dis[f]+mp[f][j];
                path[j]=f;
            }
        }
    }
}

void dfs(int x){
    dijkstra();
    if(x==k+1){                  //删k边,跑k+1次dijkstra
        ans=max(ans, dis[n]);    //dis[n]是最短路的长度,求最大值
        return ;
    }
    for(int i=n, pre=n; i; i=path[i]){
        lose[i][pre]=lose[pre][i]=1;    //枚举删除的边
        dfs(x+1);
        lose[i][pre]=lose[pre][i]=0;    //回溯
        pre=i;
    }
    return ;
}

void solve(){
    cin>>n>>k;
    memset(mp, INF, sizeof(mp));            //初始化图的距离
    memset(lose, 0, sizeof(lose));          //初始化删的边
    ans=0;
    for(int i=1; i<=n; i++) mp[i][i]=0;
    for(int i=1; i<=n*(n-1)/2; i++){
        cin>>u>>v>>w;
        mp[u][v]=mp[v][u]=w;
    }
    dfs(1);
    cout<<ans<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)   solve();
    return 0;
}

平平无奇的在校大学生