codeforce#938 (div3) 题解

C. Inhabitant of the Deep Sea

数组第一个元素减一下，最后一个元素减一下，一共能减k次，问有多少元素能减到0.细节模拟我是傻逼，有问题建议直接看tc面像tc编程

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)using namespace std;typedef long long ll;const int maxn = 2e5+5;int n;
ll k;
ll store[maxn];
int main() {IOSint t;cin>>t;while(t--) {cin>>n>>k;rep(i,0,n) cin>>store[i];ll m_right = k/2LL;ll m_left = m_right + k % 2LL;int ans = 0;int inf = 0, sup = n-1;while((m_right>0 || m_left>0) && inf<=sup) {if (inf == sup) {if (m_right + m_left >= store[inf]) {ans ++;}break;}if (m_left >= store[inf]) {ans ++;m_left -= store[inf];inf ++;} else {store[inf] -= m_left;m_left = 0;}if (m_right >= store[sup]) {ans ++;m_right -= store[sup];sup --;} else {store[sup] -= m_right;m_right = 0;}}cout<<ans<<endl;}return 0;
}

---

D. Inaccurate Subsequence Search

给数组a和数组b，问a中有多少子数组在重排后有至少k个元素相同。

滑动窗口。首先遍历b得出有多少种字母以及每个字母有多少。然后滑动窗口维护窗口内字母的个数，窗口前进时pop首位push末尾，update维护信息，然后每次窗口移动进行对比是否符合条件
finish

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)using namespace std;typedef long long ll;const int maxn = 2e5+5;const int sub_maxn = 1e6+5;int n,k,m;
int store[maxn], partten[maxn];
map<int,bool> matches;
map<int, int> used, have;
int main() {IOSint t;cin>>t;while(t--) {cin>>n>>m>>k;rep(i,0,n) cin>>store[i];rep(i,0,m) cin>>partten[i];matches.clear();used.clear();rep(i,0,m)if (matches[partten[i]]) {have[partten[i]] ++;} else {matches[partten[i]] = true;have[partten[i]] = 1;}int pos = 0,match_num = 0;int ans = 0;while(pos<n) {int num = store[pos];if (pos < m) {if (matches[num]) {if(used[num] < have[num]) match_num ++;used[num] ++;}} else {
//                cout<<"pos:"<<pos<<" match:"<<match_num<<endl;if (match_num >= k) {ans ++;}// popint pop_pos = pos - m;int pop_num = store[pop_pos];if (matches[pop_num]){used[pop_num] --;if (used[pop_num] < have[pop_num]) match_num --;}// pushif (matches[num]) {if(used[num] < have[num]) match_num ++;used[num] ++;}}pos ++;}if (match_num >= k) ans ++;cout<<ans<<endl;}return 0;
}

---

E. Long Inversions

给出一个二进制序列s，每次可以选择长度为k的连续子列取反，问能让s的每一位都变成1的最大k是多少

枚举暴力k值，倒序遍历n，发现可以直接输出。毕竟$n^2$也不大。
然后再说下怎么验证可以让s全变1.当我们在s中发现一个0，那么肯定是要反转一次的，然后继续下一位，这样全部遍历一遍看还有没有0，没有就是可以

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)using namespace std;typedef long long ll;const int maxn = 5e3+5;string store;
bool check(int);
int main() {IOSint t;cin>>t;while(t--) {int n;cin>>n;cin>>store;int inf = n;drep(inf,n,0) {if(check(inf)) {cout<<inf<<endl;break;}}}return 0;
}
bool check(int k) {int pos = 0;int len = store.length();vector<int> cnt(len+1,0);int inv_cnt = 0;bool res = true;while(pos<len) {inv_cnt += cnt[pos];int num = store[pos] - '0';if (inv_cnt%2)num = num ^ 1;if (!num) {if (pos+k<=len) {inv_cnt ++;cnt[pos+k] = -1;} else {res = false;break;}}pos ++;}return res;

---

F. Unfair Game

给一堆1234，如果这些数XOR结果是0会赢，现在每次拿走一个，问最多能赢几次。

显然4和123不属于一类，单纯考虑4，那么就赢4的个数/2次。然后我们来看123.

记dp[i][j][k]为1个数为i个，2个数为j，3个数为k时赢的次数。初始dp[0][0][0]为0。当且仅当i个1，j个2，k个3XOR时dp[i][j][k] + 1(由于XOR性质，这里只需要判断奇偶再运算就可以)，转移方程
$$dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1]$$

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)using namespace std;typedef long long ll;int p[5];
int dp[205][205][205];
void pre();
int main() {IOSpre();int t;cin>>t;while(t--) {rep(i,0,4) cin>>p[i];int ans = p[3] / 2 + dp[p[0]][p[1]][p[2]];cout<<ans<<endl;}return 0;
}
void pre() {int lim = 201;dp[0][0][0] = -1;rep(i,0,lim) {rep(j,0,lim) {rep(k,0,lim) {if (i) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);if (j) dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);if (k) dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1]);int ans = ((i&1) * 1 ) ^ ((j&1) * 2) ^ ((k&1) * 3);if (!ans)dp[i][j][k] ++;}}}
}

---

G. GCD on a grid

求从(1,1)到(n,m)的最大公约数。

这个题其实也是枚举，但是根据题意，答案一定是(1,1)和(n,m)公约数的因数。
然后我们拿着因数num对整个矩阵求余，看有没有一条路径从(1,1)到(n,m)上所有的元素都是num的倍数，如果有，那么就是候选答案，遍历所有因数后从候选答案选最大。
至于路径的查询用的dp。记dp[i][j]为(i,j)是否是因数num的倍数。当且仅当$store[i][j]\mathrm{mod}num$为true，转移方程
$$dp[i][j]=dp[i-1][j]\parallel dp[i][j-1]$$

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)using namespace std;typedef long long ll;const int maxn = 128;ll gcd(ll,ll);int n,m;
int store[maxn][maxn];
bool dp[maxn][maxn];
void init();
void show();
bool check(int);
int main() {IOSint t;cin>>t;while(t--) {cin>>n>>m;rep(i,0,n) rep(j,0,m)cin>>store[i][j];int ans = 1;int num = gcd(store[0][0], store[n-1][m-1]);int lim = sqrt(num);for(int i=1;i*i<=num;i++) {if (num % i) continue;if (check(i)) {ans = max(ans, i);}if (check(num/i))ans = max(ans, num/i);}cout<<ans<<endl;}return 0;
}
ll gcd(ll a, ll b){ll t;while(b){t = b;b = a % b;a = t;}return a;
}
void init() {rep(i,0,n) rep(j,0,m) dp[i][j] = false;
}
void show() {rep(i,0,n) {rep(j,0,m) cout<<dp[i][j]<<' ';cout<<endl;}
}
bool check(int num) {if (num == 1) return true;rep(i,0,n) {rep(j,0,m) {dp[i][j] = (store[i][j] % num) == 0;bool tmp = false;if (i && dp[i-1][j]) tmp = tmp || dp[i-1][j];if (j && dp[i][j-1]) tmp = tmp || dp[i][j-1];if (i || j) dp[i][j] = dp[i][j] && tmp;}}return dp[n-1][m-1];
}