7.28 18级杭电多校第三场

文章目录

• • 比赛过程
  • 题解
  • • 1004
    • • 题意
      • 解法
      • 代码
    • 1005
    • • 题意
      • 解法
      • 代码
    • 1009
    • • 题意
      • 解法
      • 代码
    • 1010
    • • 题意
      • 解法
      • 代码
    • 1010
    • • 题意
      • 解法
      • 代码

比赛过程

  感觉这场是手速场，三道题出的快直接100多名了，但是我今天又犯了莽的错误，罚时太多了，锅很大。。。

题解

1004

题意

  翻译过来就是给你一个序列，让你给序列分组，每一组必须是连续的元素，问你怎么分才能得到组元素之和是 $p$ 的倍数的最多组数。

解法

  贪心思想，如果某连续 $x$ 个元素的和满足条件，直接让这 $x$ 个元素为一组就可以，因为就算包含了后边的元素，他们的贡献还是 $1$。
  比赛的时候想的太复杂了，如果部分前缀和是 $sum$ 其实你只要拿 $map$ 存 $sum\mathrm{m}\mathrm{o}\mathrm{d}p$ ，然后当你发现遍历到某一个数 s u m ′ m o d p sum'\mod p sum′modp 在map里面存在就说明可以通过减去map里面那个前缀来满足条件，之后更新答案，$map$ 清空，因为你第二次遇到那个数的时候，此时的部分前缀和肯定要比第一次遇到那个数的时候大，所以肯定是可以减去的。

代码

#include
#define ll long long
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define RFOR(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
typedef pair<int,int> P;
const ll mod = 1e9+7;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[maxn];
int main(){IO;int t;cin >> t;while(t--){int n, p;cin >> n >> p;FOR(i,1,n){cin >> a[i];}map<int, int> mp;mp[0] = 1;int tmp = 0, ans = 0;FOR(i,1,n){tmp += a[i];tmp %= p;if(mp[tmp]){tmp = 0;ans++;mp.clear();mp[0] = 1;}else mp[tmp] = 1;}cout << ans << endl;}return 0;
}

1005

题意

   假如现在有两个技能，分别为 $a,b$，一个人有且只有其中的一个，现在给你一堆带技能的人，最开始所有人都不认识其他任何一个人，现在要选三个人组队，组队的要求是：1、至少有两个人的技能是 $b$，2、这三人必须都不认识。
   现在有 $n-1$ 个操作，每个操作会把两个不认识的人介绍认识，注意人与人之间的认识有传递性。求刚开始和每次操作后能够组成一队的三人组合数量。

解法

   并查集，每次连接认识的俩人在的连通块，然后减去原来两组中可以组成一队的三人组合数量，输出即可。

代码

ll Pow(ll a, ll b, ll mode)
{ll sum = 1;a = a % mode;while (b > 0){if (b % 2 == 1) //判断是否是奇数，是奇数的话将多出来的数事先乘如sumsum = (sum * a) % mode;b >>= 1;a = (a * a) % mode; // 不断的两两合并再取模，减小a和b的规模}return sum;
}
ll inv(ll x)
{return Pow(x,mode-2,mode);
}
ll pre[MAXN];
void init(int n){for(int i=1;i<=n;i++)pre[i] = i;
}
int find(int x){if(pre[x]==x) return x;return pre[x]=find(pre[x]);
}
void join(int x,int y){int fx = find(x), fy = find(y);if(fx!=fy) {pre[fy]=fx;}
}
ll ji[MAXN],cnt1[MAXN],cnt2[MAXN];
ll C(ll x,ll y)
{ll tem=(ji[y]*inv(ji[y-x])%mode)*inv(ji[x])%mode;return tem;
}
//----------------------------------------------------------------int main()
{IO;ll t;cin>>t;ji[0]=1;re(i,1,1e5+5){ji[i]=i*ji[i-1]%mode;}while(t--){int n;cin>>n;ms(cnt1,0);ms(cnt1,0);init(n+5);ll c1=0,c2=0;re(i,1,n){int a;cin>>a;if(a==1)c1++,cnt1[i]=1,cnt2[i]=0;else c2++,cnt1[i]=0,cnt2[i]=1;}ll ans=0;if(c2>=2&&c1>=1)ans=(ans+C(2,c2)*C(1,c1)%mode)%mode;if(c2>=3)ans=(ans+C(3,c2)%mode)%mode;cout<<ans<<endl;re(i,1,n-1){int u,v;cin>>u>>v;if(n-i<3){cout<<0<<endl;continue;}int fu=find(u);int fv=find(v);ll rc1=c1-cnt1[fu]-cnt1[fv];ll rc2=c2-cnt2[fu]-cnt2[fv];ll tem=0;if(cnt2[fu]>=1&&cnt1[fv]>=1)tem+=cnt2[fu]*cnt1[fv]%mode*rc2%mode;if(cnt2[fv]>=1&&cnt1[fu]>=1)tem+=cnt2[fv]*cnt1[fu]%mode*rc2%mode;if(cnt2[fv]>=1&&cnt2[fu]>=1)tem+=cnt2[fv]*cnt2[fu]%mode*((rc1+rc2)%mode)%mode;tem%=mode;ans=(ans-tem+mode)%mode;cout<<ans<<endl;cnt2[fu]+=cnt2[fv];cnt1[fu]+=cnt1[fv];join(u,v);}}}

1009

题意

  给你一个包含 三种元素的字符串，比如 $((\ast \ast \ast )()((\ast \ast$，其中 $\ast$ 可以变成 $)($ 中任意一个或者直接删掉，问你能得到的最短的括号平衡串的长度，长度相同的话选择字典序最小的。

解法

  其实只要正序逆序各处理一边就可以了，正序处理是让所有的 $)$ 满足要求，逆向是让所有的 $($ 满足要求。

代码

#include
#define ll long long
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define RFOR(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
typedef pair<int,int> P;
const ll mod = 1e9+7;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int main(){IO;int t;cin >> t;while(t--){string s;cin >> s;int n = s.size();int f = 0;deque<int> q;FOR(i,0,n-1){if(s[i]=='(') f++;else if(s[i]==')') f--;else{q.push_back(i);}if(f<0){if(q.size()>0){f++;int pos = q.front();q.pop_front();s[pos] = '(';}else break;}}if(f<0) {cout << "No solution!" << endl;continue;}int x = 0;RFOR(i,n-1,0){if(f==0) break;if(s[i]=='('){x--;if(x<0) break;}else if(s[i]=='*') {f--;x++;s[i] = ')';}else x++;}if(f>0) {cout << "No solution!" << endl;continue;}FOR(i,0,n-1){if(s[i]!='*')cout << s[i];}cout << endl;}return 0;
}

1010

题意

解法

代码

1010

题意

解法

代码

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！