什么网站可以做线上小游戏,企业官网制作公司,c2c网站架构,wordpress权限说明C. Inhabitant of the Deep Sea
数组第一个元素减一下#xff0c;最后一个元素减一下#xff0c;一共能减k次#xff0c;问有多少元素能减到0.细节模拟我是傻逼#xff0c;有问题建议直接看tc面像tc编程
#include iostream
#include string.h
#include 最后一个元素减一下一共能减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 2e55;int n;
ll k;
ll store[maxn];
int main() {IOSint t;cint;while(t--) {cinnk;rep(i,0,n) cinstore[i];ll m_right k/2LL;ll m_left m_right k % 2LL;int ans 0;int inf 0, sup n-1;while((m_right0 || m_left0) infsup) {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;}}coutansendl;}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 2e55;const int sub_maxn 1e65;int n,k,m;
int store[maxn], partten[maxn];
mapint,bool matches;
mapint, int used, have;
int main() {IOSint t;cint;while(t--) {cinnmk;rep(i,0,n) cinstore[i];rep(i,0,m) cinpartten[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(posn) {int num store[pos];if (pos m) {if (matches[num]) {if(used[num] have[num]) match_num ;used[num] ;}} else {
// coutpos:pos match:match_numendl;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 ;coutansendl;}return 0;
}E. Long Inversions
给出一个二进制序列s每次可以选择长度为k的连续子列取反问能让s的每一位都变成1的最大k是多少
枚举暴力k值倒序遍历n发现可以直接输出。毕竟 n 2 n^2 n2也不大。 然后再说下怎么验证可以让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 5e35;string store;
bool check(int);
int main() {IOSint t;cint;while(t--) {int n;cinn;cinstore;int inf n;drep(inf,n,0) {if(check(inf)) {coutinfendl;break;}}}return 0;
}
bool check(int k) {int pos 0;int len store.length();vectorint cnt(len1,0);int inv_cnt 0;bool res true;while(poslen) {inv_cnt cnt[pos];int num store[pos] - 0;if (inv_cnt%2)num num ^ 1;if (!num) {if (posklen) {inv_cnt ;cnt[posk] -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个数为j3个数为k时赢的次数。初始dp[0][0][0]为0。当且仅当i个1j个2k个3XOR时dp[i][j][k] 1(由于XOR性质这里只需要判断奇偶再运算就可以)转移方程 d p [ i ] [ j ] [ k ] m a x ( d p [ i − 1 ] [ j ] [ k ] , d p [ i ] [ j − 1 ] [ k ] , d p [ i ] [ j ] [ k − 1 ] dp[i][j][k] max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1] 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;cint;while(t--) {rep(i,0,4) cinp[i];int ans p[3] / 2 dp[p[0]][p[1]][p[2]];coutansendl;}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 ((i1) * 1 ) ^ ((j1) * 2) ^ ((k1) * 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的倍数。当且仅当 s t o r e [ i ] [ j ] m o d n u m store[i][j] \mod num store[i][j]modnum为true转移方程 d p [ i ] [ j ] d p [ i − 1 ] [ j ] ∥ d p [ i ] [ j − 1 ] dp[i][j] dp[i-1][j] \parallel dp[i][j-1] dp[i][j]dp[i−1][j]∥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;cint;while(t--) {cinnm;rep(i,0,n) rep(j,0,m)cinstore[i][j];int ans 1;int num gcd(store[0][0], store[n-1][m-1]);int lim sqrt(num);for(int i1;i*inum;i) {if (num % i) continue;if (check(i)) {ans max(ans, i);}if (check(num/i))ans max(ans, num/i);}coutansendl;}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) coutdp[i][j] ;coutendl;}
}
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];
}
