codeforce#938 (div3) 题解

发布于：2024-05-08 ⋅ 阅读:(20) ⋅ 点赞:(0)

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() {
    IOS
    
    int 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() {
    IOS
    
    int 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 ++;
                }
                // pop
                int 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 --;
                }
                
                // push
                if (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 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 = 5e3+5;

string store;
bool check(int);
int main() {
    IOS
    
    int 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性质，这里只需要判断奇偶再运算就可以)，转移方程
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() {
    IOS
    
    pre();
    
    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的倍数。当且仅当 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() {
    IOS
    
    int 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];
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布