Educational Codeforces Round 155 (Rated for Div. 2)(A

Educational Codeforces Round 155 (Rated for Div. 2)(A

文章目录

• • A. Rigged!
  • B. Chips on the Board
  • C. Make it Alternating
  • D. Sum of XOR Functions

A. Rigged!

签到。我们贪心的想，让此时的重量为第一个人的的重量 w 1 w_1 w1​，若在 2 − n 2-n 2−n中存在某个人的重量大于 w 1 w_1 w1​并且耐力比第一个人还要久，那么输出-1即可。

#include <bits/stdc++.h>using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;void solve()
{int n;cin>>n;vector<pll> a(n+5);for(int i=1;i<=n;i++) {int x,y;cin>>x>>y;a[i]={x,y};}int v=a[1].second;ll ans=a[1].first;for(int i=2;i<=n;i++){auto [x,y]=a[i];if(y>=v&&x>=ans){cout<<-1<<endl;return ;}}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}

B. Chips on the Board

签到。我们发现只要满足对 n n n列来说，只要每一行至少存在一个数就算合法，对于 n n n行而言同理。

#include <bits/stdc++.h>using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;void solve()
{int n;cin>>n;vector<ll> a(n+5),b(n+5);ll sum1=0,sum2=0;ll m1=2e9,m2=2e9;for(int i=0;i<n;i++){cin>>a[i];sum1+=a[i];m1=min(m1,a[i]);}for(int i=0;i<n;i++){cin>>b[i];sum2+=b[i];m2=min(m2,b[i]);}ll ans=min(m1*n+sum2,m2*n+sum1);cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}

C. Make it Alternating

题意：
给你一个二进制字符串 s s s。二进制字符串是由字符 0 和/或 1 组成的字符串。

您可以对 s s s 执行以下操作 （即使是零） 的任意次数：

• 选择一个整数 i i i，使得 1 ≤ i ≤ ∣ s ∣ 1 le i le |s| 1≤i≤∣s∣，然后擦除字符 s i s_i si​。

您必须让 s s s交替出现，也就是说，在您执行操作后， s s s中每两个相邻的字符应该是不同的。

您的目标是计算两个值：

• 使 s s s 交替出现所需的最少操作次数；
• 使 s s s 交替出现的最短操作序列的个数。如果在这两个操作序列中，至少有一个操作所选择的整数 i i i 是不同的，那么这两个操作序列就是不同的。

思路：
对于第一问十分简单，我们只需要计算相同的所有相同的块变为1的数量。
第二问：考虑对于每组块内的删除，若一组块的个数为3，那么该组块有3种删法，根据乘法原理我们可以知道，若我们有 n n n组块，每组块有 a i a_i ai​个，那么我们是删除方法有 ∏ i = 0 n a i prod_{i=0}^n{a_i} ∏i=0n​ai​种，又因为题目要求为排列，所以再乘以所有块数的阶乘即可。

#include <bits/stdc++.h>using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;void solve()
{string s;cin>>s;int cnt=1;vector<int> a;for(int i=1;i<s.size();i++){if(s[i]==s[i-1]) cnt++;else {a.push_back(cnt);cnt=1;}}if(cnt>1) a.push_back(cnt);ll ans1=0,ans2=1;for(auto x: a){ans1+=(x-1);ans1%=mod;ans2=ans2*x%mod;}for(int i=1;i<=ans1;i++){ans2=ans2*i%mod;}cout<<ans1<<" "<<ans2<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;cin>>t;while (t--){solve();}system("pause");return 0;
}

D. Sum of XOR Functions

题意：
给你一个长度为 n n n 的数组 a a a ，由非负整数组成。

您必须计算 ∑ l = 1 n ∑ r = l n f ( l , r ) ⋅ ( r − l + 1 ) sum_{l=1}^{n} sum_{r=l}^{n} f(l, r) cdot (r - l + 1) ∑l=1n​∑r=ln​f(l,r)⋅(r−l+1) 的值，其中 f ( l , r ) f(l, r) f(l,r) 是 a l ⊕ a l + 1 ⊕ ⋯ ⊕ a r − 1 ⊕ a r a_l oplus a_{l+1} oplus dots oplus a_{r-1} oplus a_r al​⊕al+1​⊕⋯⊕ar−1​⊕ar​（字符 ⊕ oplus ⊕ 表示位向 XOR）。

由于答案可能非常大，因此请打印它的模数 998244353 998244353 998244353。

思路：拆位算贡献
s k = ⨁ i = 1 k a i f ( l , r ) = ⨁ i = l r a i = s r ⊕ s l − 1 begin{align*} s_k &= bigoplus_{i=1}^ka_i \ f(l,r) &= bigoplus_{i=l}^r a_i \ &= s_r oplus s_{l-1} end{align*} sk​f(l,r)​=i=1⨁k​ai​=i=l⨁r​ai​=sr​⊕sl−1​​
a n s = ∑ l = 1 n ∑ r = l n f ( l , r ) ⋅ ( r − l + 1 ) = ∑ l = 1 n ∑ r = l n f ( l , r ) ⋅ r − f ( l , r ) ⋅ ( l − 1 ) = ∑ l = 0 n ∑ r = l n ( ∑ i = 0 32 2 i ∗ ( ( s r & 2 i ) ⊕ ( s l & 2 i ) ) ∗ ( r − l ) ) begin{align*} ans &= sum_{l= 1}^nsum_{r=l}^n f(l,r)cdot(r - l + 1) \ &= sum_{l= 1}^nsum_{r=l}^n f(l,r)cdot r- f(l,r)cdot (l - 1)\ &= sum_{l= 0}^nsum_{r=l}^n (sum_{i = 0} ^ {32} 2^{i} * ((s_r & 2^i) oplus (s_l &2^i))*(r - l))\ end{align*} ans​=l=1∑n​r=l∑n​f(l,r)⋅(r−l+1)=l=1∑n​r=l∑n​f(l,r)⋅r−f(l,r)⋅(l−1)=l=0∑n​r=l∑n​(i=0∑32​2i∗((sr​&2i)⊕(sl​&2i))∗(r−l))​

那么每个数每一位的贡献为：

r e s = 2 i [ ( r − l 1 ) + ( r − l 2 ) + . . . + ( r − l k ) ] = 2 i [ k r − ∑ i = 1 k l i ] begin{align*} res& =2^i [(r-l_1) + (r - l_2) + ... + (r - l _k)]\ &=2^i[kr - sum_{i = 1}^kl_i] end{align*} res​=2i[(r−l1​)+(r−l2​)+...+(r−lk​)]=2i[kr−i=1∑k​li​]​

#include <bits/stdc++.h>using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;ll f[N][35], c[N][35];void solve()
{int n;cin >> n;vector<ll> a(n + 5);vector<ll> s(n + 5);for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)s[i] = s[i - 1] ^ a[i];ll ans = 0;for (int i = 0; i <= n; i++){for (int j = 0; j <= 30; j++){f[j][(s[i] >> j) & 1]=(f[j][(s[i] >> j) & 1]+1)%mod;c[j][(s[i] >> j) & 1]=(c[j][(s[i] >> j) & 1]+i)%mod;}for (int j = 0; j <= 30; j++){ans = (ans + (1ll << j)%mod * ((f[j][(s[i] >> j & 1) ^ 1]%mod * (ll)i - c[j][(s[i] >> j & 1) ^ 1])%mod+mod) % mod) % mod;}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin>>t;while (t--){solve();}system("pause");return 0;
}