观察到对行的dp和列的dp互不影响，工人只能用一次的性质

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> h(n, vector<int>(n));

    for (auto& r : h) {
        for (auto& v : r) {
            cin >> v;
        }
    }

    vector<int> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;

    vector<array<array<bool, 2>, 2>> ok_r(n-1);
    for (int i = 0; i < n-1; ++i) {
        bool has0 = false, has1 = false, hasf1 = false;
        for (int j = 0; j < n; ++j) {
            int diff = h[i][j] - h[i+1][j];
            has0 |= (diff == 0);
            has1 |= (diff == 1);
            hasf1 |= (diff == -1);
        }
        ok_r[i][0][0] = !has0;
        ok_r[i][0][1] = !has1;
        ok_r[i][1][0] = !hasf1;
        ok_r[i][1][1] = !has0;
    }

    array<int, 2> dp_hang_pre = {0, a[0]};
    for (int i = 1; i < n; ++i) {
        array<int, 2> dp_hang_cur = {INF, INF};
        for (int x_pre : {0, 1}) {
            if (dp_hang_pre[x_pre] == INF) continue;
            for (int x_cur : {0, 1}) {
                if (ok_r[i-1][x_pre][x_cur]) {
                    int cost = dp_hang_pre[x_pre] + (x_cur ? a[i] : 0);
                    dp_hang_cur[x_cur] = min(dp_hang_cur[x_cur], cost);
                }
            }
        }
        dp_hang_pre = dp_hang_cur;
    }
    int hang_min = min(dp_hang_pre[0], dp_hang_pre[1]);

    vector<array<array<bool, 2>, 2>> ok_c(n-1);
    for (int j = 0; j < n-1; ++j) {
        bool has0 = false, has1 = false, hasf1 = false;
        for (int i = 0; i < n; ++i) {
            int diff = h[i][j] - h[i][j+1];
            has0 |= (diff == 0);
            has1 |= (diff == 1);
            hasf1 |= (diff == -1);
        }
        ok_c[j][0][0] = !has0;
        ok_c[j][0][1] = !has1;
        ok_c[j][1][0] = !hasf1;
        ok_c[j][1][1] = !has0;
    }

    array<int, 2> dp_lie_pre = {0, b[0]};
    for (int j = 1; j < n; ++j) {
        array<int, 2> dp_lie_cur = {INF, INF};
        for (int y_pre : {0, 1}) {
            if (dp_lie_pre[y_pre] == INF) continue;
            for (int y_cur : {0, 1}) {
                if (ok_c[j-1][y_pre][y_cur]) {
                    int cost = dp_lie_pre[y_pre] + (y_cur ? b[j] : 0);
                    dp_lie_cur[y_cur] = min(dp_lie_cur[y_cur], cost);
                }
            }
        }
        dp_lie_pre = dp_lie_cur;
    }
    int lie_min = min(dp_lie_pre[0], dp_lie_pre[1]);

    if (hang_min == INF || lie_min == INF) {
        cout << "-1\n";
    } else {
        cout << hang_min + lie_min << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

}

灯泡题套路,一个通用的思路的就是根据图来观察奇偶性，观察下列图
发现横向是加2，竖向有2有1，斜向是2.所以出x，在搞y。
首先行向必须是奇数，其次发现存在x+y（原始）的一直不变量，并且是奇数个（其他都是偶数个）。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

void solve() {
    int n;
    cin >> n;
    vector<pii> vc(n);
    map<int,int> mpx,mpxy;

    for(auto &[x,y]:vc){
        cin>>x>>y;
        mpx[x]++;
        mpxy[x+y]++;
    }
    int xx=0;
    int yy=0;
    for(auto [x,y]:vc){
        if(mpx[x]&1){
            xx=x;
        }
    }
     for(auto [xy,cnt]:mpxy){
        if((cnt)&1){
            yy=xy-xx;
        }
    }
    cout<<xx<<" "<<yy<<"\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

简单的二分查找位置，但是这个用栈来搞字符串真牛啊，（删除若干个字符）生成最小字符串，采用单调栈，因为字符串具有字符本身权值，单先后优先级比较高

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    int pos;
    cin >> s >> pos;
    int n = s.size();

     int l=0, r=n, m=0;
    while(l<=r) {
        int mid=(l+r)/2;
        int sum=mid*(2*n - mid +1)/2; 
        if(sum < pos) {m=mid; l=mid+1;}
        else r=mid-1;
    }

    int sum_m=m*(2*n -m +1)/2;
    int pos_in_layer=pos - sum_m;
    int k=m; 


    string res;
    for(int i=0; i<s.size(); ++i) {
        while(k>0 && !res.empty() && res.back()>s[i]) {
            res.pop_back();
            k--;
        }
        res.push_back(s[i]);
    }
    while(k>0) {
        res.pop_back();
        k--;
    }

    cout << res[pos_in_layer-1];
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin>>t; while(t--) solve();
}

边界处麻烦的一道题，我们只需要关注左右的》《符号个数，前缀和记录个数，和位移。二分查找到抵消的前缀就行

一道思路很灵活的组合计数题

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int power(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = 1LL * ans * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return ans;
}

int inverse(int a) {
    return power(a, MOD - 2);
}

int main() {
    int n, m;
    cin >> n >> m;

    string s;
    cin >> s;

    int ans = 1;


    for (int i = 1; i < s.size(); ++i) {  
        if (s[i] == '?') {
            ans = 1LL * ans * (i) % MOD;  // 第i+1次插入，可用间隙数 = i
        }
    }


    cout << (s[0] == '?' ? 0 : ans) << '\n';

    while (m--) {
        int pos;
        char c;
        cin >> pos >> c;
        pos--; // 转换为0-based索引


        if (s[pos] != c) {

            if (pos > 0 && s[pos] == '?') {
                ans = 1LL * ans * inverse(pos) % MOD;
            }


            s[pos] = c;

            if (pos > 0 && s[pos] == '?') {
                ans = 1LL * ans * pos % MOD;
            }
        }

        cout << (s[0] == '?' ? 0 : ans) << '\n';
    }

    return 0;
}

巨妙的一道组合数学题

//题意提示采用n方,不妨枚举长度l和贡献v(l+1,2*l+1),那么数组b中肯定不出现l个数小于v,也就是v-l-1个小于v,那么就有l-(v-l-1)个大于v,那么直接在n里面组合

数学约束解答(隔板法)

又来字典序栈维护题?超绝puls版本

//维护奇偶波动序列,首先选择的数字的一定的,但是相对位置有区别.
//贪心的想越靠前,保证奇数位越大,偶数位更小.那么为了保证这个相对顺序的限制,我们要保证选完ans
//中的第i个的时候要保证,后面还要至少m-i个可以选,一开始我只用用后缀数组维护种类个数,和最后一
//个次
//出现的种类测试,但是对于3 1 2 3这样子的样例,不能正确保证,还有至少m-i个可以选,正确应该
//维护每个元素出现的最后出现的位置,如果要把,如果要把改元素pop,应该保证后面还有改元素出现.
//至于为什么采用单双pop,是因为单pop只能保证前一位最优(只保证奇或者偶数),双pop保证更近一位
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> last(n + 1, -1); // 元素值从1到n，记录最后出现的位置

    for (int i = 0; i < n; ++i) {
        cin>>a[i];
        last[a[i]] = i; // 更新元素a[i]的最后出现位置为i
    }

    vector<int> sta;
    vector<bool> inStack(n + 1, false); // 标记元素是否在栈中

    for (int i = 0; i < n; ++i) {
        int num = a[i];
        if (inStack[num]) continue;

        // 单元素弹出：检查栈顶元素是否需要弹出
        while (!sta.empty()) {
            int top = sta.back();
            int stackSize = sta.size();
            bool shouldPop = false;

            // 根据栈大小的奇偶性决定比较方向
            if (stackSize % 2 == 0) { // 下一个位置是奇数位，需要更大
                shouldPop = (num < top);
            } else { // 下一个位置是偶数位，需要更小
                shouldPop = (num > top);
            }

            if (shouldPop && last[top] > i) { // 栈顶元素之后还有出现机会
                inStack[top] = false;
                sta.pop_back();
            } else {
                break;
            }
        }

        // 双元素弹出：检查是否需要弹出前两个元素
        while (sta.size() >= 2) {
            int top1 = sta.back();
            sta.pop_back();
            int top2 = sta.back();

            int stackSize = sta.size(); // 弹出top1后的大小
            bool shouldPop = false;

            if ((stackSize+1) % 2 == 0) { // 下一个位置是奇数位，需当前num > top2
                shouldPop = (num > top2);
            } else { // 下一个位置是偶数位，需当前num < top2
                shouldPop = (num < top2);
            }

            if (shouldPop && last[top2] > i && last[top1] > i) {
                inStack[top1] = false;
                inStack[top2]=false;
                sta.pop_back(); // 弹出top2
            } else {
                sta.push_back(top1); // 恢复top1
                break;
            }
        }

        sta.push_back(num);
        inStack[num] = true;
    }

    cout<<sta.size()<<"\n";
    for (int num : sta) {
        cout<<num<<" ";
    }
    cout<<"\n";
}

int main() {
    int t;
    cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}
//线段树维护版本
//直接对ans的第i个经行单处理,根据奇偶性选最大
//根据ans中上一个(i-1)已经选的元素位置last,然后查询选

思考方式

观察性质:奇数和偶数产生奇数
中间:偶数是不断被消耗的
得出结论:不断枚举偶数

cf1019,今晚爆a,值得深思,最近训练太少了
分前后,前中,中后三种情况,前后缀不必去找中位数,直接把大于的赋值1,小于1的赋值-1,然后找两次整数就行;其实就是当两端前缀prea,preb的值都小于k的时候,a和a~b也算同理的

第一次过1900,kuasl算法变种

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int p[2001];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void solve() {
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        p[i]=i;
    }

    vector<pii> ans;
    // for(auto [i,j]:a){
    //     cout<<i<<" "<<j<<"pp\n";
    // }
    for(int i=n-1;i>=1;i--){
        map<int,int> mp;
        bool ok=false;
       // cout<<i<<"ii\n";
        for(int j=1;j<=n;j++){
            if(mp[(a[j])%i]){
                //cout<<a[j].second<<" "<<mp[(a[j].second)%i]<<"\n";
                int fj=find(j);
                int fl=find(mp[(a[j])%i]); 
                if(fj==fl){
                    continue;
                }else{
                    ans.push_back({j, mp[(a[j])%i]});
                    //cout<<a[j].second<<" "<<mp[(a[j].second)%i]<<"\n";
                    p[fj]=fl;
                    ok=true;
                    break;
                }
            }else{
                mp[(a[j])%i]=j;
            }
        }
        if(!ok){
            cout<<"NO\n";
            return;
        }
    } 
    cout<<"yes\n";
    reverse(ans.begin(),ans.end());
    for(auto [i,j]:ans){
        cout<<i<<" "<<j<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

水题,但是翻译翻错

差一个大胆和细节的敲:

//不难知道,有唯一最优操作,先1后2,但是对于区间的查询,对越两侧边界很难处理
//想多多维前缀和,但是情况要怎么分的清楚,由于前缀和只能用于计算一层的贡献
//为了防止嵌套循环,统一计算所有对s(a字符串)的贡献,
//所有要列举所有的情况:(且互斥)
//:计算原始的a的1的个数
//1:?0?->?1?(单层b对a的贡献)
//  101  101
//2:?000->1100(a->b->a)加载i-3左边
//  1000  1010
//3:000?->011?(a->b->a)加载i-3右边
//  0001  0101
//4:0?0?0->0?1?0-(加中间)
//  ?0?0?  ?1?1?
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 200005;
int T, n, q, l, r;
int sum1[MAXN], sum2[MAXN], sum3[MAXN], sum4[MAXN], sum5[MAXN];
char s[MAXN], t[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> (s + 1) >> (t + 1);

        for (int i = 1; i <= n; i++) {
            // Original 1s in s
            sum1[i] = sum1[i - 1] + (s[i] - '0');

            if (i <= 2) continue;
            // Case (a,a)
            sum2[i] = sum2[i - 1];
            if (t[i - 2] == '1' && t[i] == '1' && s[i - 1] == '0')
                sum2[i]++;

            if (i <= 3) continue;
            // Case (a,b)
            sum3[i] = sum3[i - 1];
            if (s[i] == '0' && s[i - 2] == '0' && t[i - 3] == '1' && t[i - 1] == '0')
                sum3[i]++;

            // Case (b,a)
            sum4[i] = sum4[i - 1];
            if (t[i] == '1' && t[i - 2] == '0' && s[i - 1] == '0' && s[i - 3] == '0')
                sum4[i]++;

            if (i <= 4) continue;
            // Case (b,b)
            sum5[i] = sum5[i - 1];
            if (s[i] == '0' && s[i - 2] == '0' && s[i - 4] == '0' && t[i - 1] == '0' && t[i - 3] == '0')
                sum5[i]++;
        }

        cin >> q;
        while (q--) {
            cin >> l >> r;

            int ans = sum1[r] - sum1[l - 1];
            //注意有于t1之和i以及前两个元素有关,所有要调整为l+1;        
            if (l + 2 <= r) ans += sum2[r] - sum2[l + 1];
            if (l + 3 <= r) ans += sum3[r] - sum3[l + 2] + sum4[r] - sum4[l + 2];
            if (l + 4 <= r) ans += sum5[r] - sum5[l + 3];

            cout << ans << '\n';
        }
    }

    return 0;
}

不难发现度数有规律,但是验证和更新复杂度qn,采用神奇的度数转权值(只需要直接对父节点和当前节点操作,不许对所有相邻节点)

tle
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> adj[200001];

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) adj[i].clear();
    vector<int> a(n+1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 0; i < n-1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    unordered_map<int, int> mp;
    unordered_map<int, int> degree;
    unordered_map<int, int> cnt;

    for (int i = 1; i <= n; ++i) {
        if (a[i]) mp.insert({i, 1});
    }
    for (auto &node : mp) {
        int u = node.first;
        int d = 0;
        for (int v : adj[u]) {
            if (mp.count(v)) ++d;
        }
        degree[u] = d;
        cnt[d]++;
    }

    while (q--) {
        int x; cin >> x;
        if (mp.count(x)) {
            int d = degree[x];
            cnt[d]--;
            if (cnt[d] == 0) cnt.erase(d);
            for (int v : adj[x]) {
                if (mp.count(v)) {
                    int old = degree[v];
                    cnt[old]--;
                    if (cnt[old] == 0) cnt.erase(old);
                    degree[v]--;
                    cnt[degree[v]]++;
                }
            }
            mp.erase(x);
            degree.erase(x);
        } else { 
            mp[x] = 1;
            int d = 0;
            for (int v : adj[x]) {
                if (mp.count(v)) {
                    int old = degree[v];
                    cnt[old]--;
                    if (cnt[old] == 0) cnt.erase(old);
                    degree[v]++;
                    cnt[degree[v]]++;
                    d++;
                }
            }
            degree[x] = d;
            cnt[d]++;
        }

        int k = mp.size();
        if (k <= 1) {
            if(k)
            cout << "YES\n";
            else
            cout << "NO\n";
        } else {
            int c1 = cnt.count(1) ? cnt[1] : 0;
            int c2 = cnt.count(2) ? cnt[2] : 0;
            if (c1 == 2 && c2 == (k - 2) && (c1 + c2) == k) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}
//权值转化,检查但项链和双向
#include<bits/stdc++.h>
using namespace std;

// 全局变量定义
int T,n,q,i,j;
int u,v;
vector<int> e[214514];  // 邻接表存储树结构
int f[214514],c[214514],val[214514],tong[414514]; // f:父节点, c:颜色, val:权值, tong:权值计数
set<int> one;  // 存储权值为1的节点
set<int>::iterator it;

// DFS预处理父节点关系
void dfs(int u,int fa) {
    f[u]=fa;
    for(auto v:e[u]) if(v!=fa) dfs(v,u);
}

int main() {
    cin>>T;
    while(T--) {
        cin>>n>>q;
        // 输入节点颜色
        for(i=1;i<=n;i++) cin>>c[i];
        // 构建树结构
        for(i=1;i<n;i++) {
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        // 预处理父节点关系
        dfs(1,0);
        tong[n]=n+1;  // 初始化权值计数数组

        // 初始权值计算
        for(i=1;i<=n;i++) if(c[i]) {
            int fa=f[i];
            tong[val[i]+n]--, tong[val[fa]+n]--;
            tong[--val[i]+n]++, tong[++val[fa]+n]++;
            if(val[fa]==1) one.insert(fa);
            if(val[i]==1) one.insert(i);
            if(val[fa]==2) one.erase(fa);
            if(val[i]==0) one.erase(i);
        }

        // 处理查询
        while(q--) {
            int x;
            cin>>x;
            i=x;
            int fa=f[i];
            // 切换节点颜色（黑变白或白变黑）
            if(c[i]) swap(i,fa), c[fa]^=1;
            else c[i]^=1;

            // 更新权值
            tong[val[i]+n]--, tong[val[fa]+n]--;
            tong[--val[i]+n]++, tong[++val[fa]+n]++;

            // 更新权值为1的节点集合
            if(val[fa]==1) one.insert(fa);
            if(val[i]==1) one.insert(i);
            if(val[fa]==2) one.erase(fa);
            if(val[i]==0) one.erase(i);

            // 检查链条件
            int tg=0;
            // 单方向链情况
            if(tong[n]==n-1 && tong[n-1]==1 && tong[n+1]==1) tg=1;
            // 双向链情况
            if(tong[n]==n-3 && tong[n-1]==2 && tong[n+1]==2) {
                it=one.begin(); u=*it; it++; v=*it;
                if((f[u]==v || f[v]==u) && (c[u] || c[v])) tg=1;
            }
            cout<<(tg?"Yes":"No")<<endl;
        }

        // 清空数据结构，准备下一测试用例
        for(i=0;i<=n+5;i++) e[i].clear(), f[i]=c[i]=val[i]=0;
        for(i=0;i<=2*n+5;i++) tong[i]=0;
        one.clear();
    }
    return 0;
}