找连续且长度大于等于a的子串长度和。直接记录加和即可。

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

const int N = 1e5 + 10;
int a[N];

inline void solve(){
    int n = 0; cin >> n;
    string s; cin >> s, s = '@' + s;
    int cnt = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        if(s[i] == 'a') cnt++;
        else{
            if(cnt >= 2) ans += cnt;
            cnt = 0;
        }
    }
    if(cnt >= 2) ans += cnt;
    cout << ans << endl;
}


signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

数位DP，队友过的

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;
int l1,r1,l2,r2,l3,r3;
int dp[40][10];
int way[]={0,3,5,6};
int qpow(int x,int y,int res=1){
    for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod;
    return res;
}
int ck(int x,int y,int z){
    int res=0;
    for(int i=0;i<3;i++){
        int fg1=((x>>i)&1),fg2=((y>>i)&1),fg3=((z>>i)&1);
        if(fg1!=fg2){
            res+=(fg1<<i);
        }
        else{
            res+=(fg3<<i);
        }
    }
    return res;
}
int dfs(int x,int y,int z){
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    for(int i=0;i<32;i++){
        int fg1=((x>>i)&1),fg2=((y>>i)&1),fg3=((z>>i)&1);
        int now=fg1*4+fg2*2+fg3;
        for(auto t:way){
            for(int j=0;j<8;j++){
                (dp[i+1][ck(t,now,j)]+=dp[i][j])%=mod;
            }
        }
    }
    return dp[32][0];
}
inline void solve(){
    cin>>l1>>r1>>l2>>r2>>l3>>r3;
    int ans1=dfs(r1,r2,r3),
        ans2=dfs(r1,r2,l3-1),
        ans3=dfs(r1,l2-1,r3),
        ans4=dfs(r1,l2-1,l3-1),
        ans5=dfs(l1-1,r2,r3),
        ans6=dfs(l1-1,r2,l3-1),
        ans7=dfs(l1-1,l2-1,r3),
        ans8=dfs(l1-1,l2-1,l3-1);
    int fenzi=((ans1-ans2-ans3+ans4-ans5+ans6+ans7-ans8)%mod+mod)%mod;
    int fenmu=(r1-l1+1)*(r2-l2+1)%mod*(r3-l3+1)%mod;
    cout<<(mod+1-fenzi*qpow(fenmu,mod-2)%mod)%mod;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

模拟题，模拟区域裁剪。注意首先要把周边没有用的给裁掉。

记$vis[i][j]$表示第$(i,j)$位置的方格是否已经被裁剪，然后遍历每个点，对没裁过的点扫描线算面积，最后取最大值即可。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;

struct point { int x, y; } p[N];
struct line { point st, ed; } l[N];

int col[1010][1010], row[1010][1010];

bool check (int x, int y){
	return (1 <= x) && (1000 >= x) && (1 <= y) && (1000 >= y);
}

bool vis[1010][1010];
int cal[N];

int getpos(int x, int y) { return x * 1001 + y; }

int find(int x, int y){
    if(vis[x][y]) return 0;
    vis[x][y] = 1, cal[1] = x * 1001 + y;;
    int cnt = 1;
    
    for(int st = 1, ed = 2; st < ed; st++){
        int nx = cal[st] / 1001, ny = cal[st] % 1001;
        if(check(nx, ny + 1) && !row[nx][ny] && !vis[nx][ny + 1]){
            vis[nx][ny + 1] = 1, cal[ed++] = getpos(nx, ny + 1), ++cnt;
        }
        if(check(nx, ny - 1) && !row[nx][ny - 1] && !vis[nx][ny - 1]){
            vis[nx][ny - 1] = 1, cal[ed++] = getpos(nx, ny - 1), ++cnt;
        }
        if(check(nx + 1, ny) && !col[nx][ny] && !vis[nx + 1][ny]){
            vis[nx + 1][ny] = 1, cal[ed++] = getpos(nx + 1, ny), ++cnt;
        }
        if(check(nx - 1, ny) && !col[nx - 1][ny] && !vis[nx - 1][ny]){
            vis[nx - 1][ny] = 1, cal[ed++] = getpos(nx - 1, ny), ++cnt;
        }
    }
    return cnt;
}

inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n + 1; i++) cin >> p[i].x >> p[i].y;
    int lastx = 0, lasty = 0;
    for(int i = 1; i <= n; i++){
        if(p[i].x == p[i + 1].x){
            int st = min(p[i].y, p[i + 1].y) + 1, ed = max(p[i].y, p[i + 1].y);
            for(int j = st; j <= ed; j++) col[p[i].x][j] = 1;
        } else {
            int st = min(p[i].x, p[i + 1].x) + 1, ed = max(p[i].x, p[i + 1].x);
            for(int j = st; j <= ed; j++) row[j][p[i].y] = 1;
        }
    }
    int ans = 0;
    find(1, 1);
    for(int i = 1; i <= 1000; i++){
        for(int j = 1; j <= 1000; j++) ans = max(ans, find(i, j));
    }
    cout << ans << endl;
}



signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

队友猜了个结论过了

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int h[N];

inline void solve(){
    int n,x,y;
    cin>>n>>x>>y;
    int cnt=0;
    for(;x%2==0&&y%2==0;cnt++,x/=2,y/=2);
    cout<<n-cnt-1;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

可以发现本质是求给定序列中单调递减且公差为$1$的最长等差子序列个数，直接开桶计数一下即可。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;
int a[N], b[N];

inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
        if(b[a[i] + 1]) b[a[i] + 1] -= 1;
        b[a[i]] += 1;
    }
    int ans = 0;
    for(int i = 1; i <= 1e6; i++) ans += b[i];
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

注意到每个字符串的长度非常小，且仅含一个*，那么对每个字符串枚举26种可能的*填充，然后全部插入字典树，字典树叶子节点带权，然后求出权值最大的叶节点到根节点的路径即可，最大的权值即为满足条件的个数。

可以发现，当某条路径被经过次数最多时，这条路径就是答案，求最大的叶子节点就是基于这个思想。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e6 + 10, MOD = 1e9 + 7;

namespace Trie{
    int tot, ch[N][27], fa[N], cnt[N], maxx, max_pos, max_dep; 

    string ans;

    int getnum(char x){ return x - 'a'; }

    void insert(string str) {
        int rt = 0, len = str.length();
        for(int i = 0; i < len; i++){
            int c = getnum(str[i]);
            if(!ch[rt][c]) ch[rt][c] = ++tot, fa[tot] = rt;
            rt = ch[rt][c];
            if(i + 1 == len) cnt[rt]++;
        }
    }

    void clc(int dep){ maxx = -1, max_pos = -1, max_dep = dep; }

    void find_max(int rt, int dep){
        if(dep == max_dep){
            if(cnt[rt] > maxx) maxx = cnt[rt], max_pos = rt;
            return;
        }
        for(int i = 0; i < 26; i++){
            if(ch[rt][i]) find_max(ch[rt][i], dep + 1);
        }
    }

    void get(int rt = max_pos){
        while(rt>1){
            for(int i = 0; i < 26; i++){
                if(ch[fa[rt]][i] == rt) ans += (char)('a' + i);
            }
            rt = fa[rt];
        }
        reverse(ans.begin(), ans.end());
    }
} 

inline void solve(){
    int n, c; cin >> n >> c;
    for(int i = 1; i <= n; i++){
        string s; cin >> s;
        s = "a" + s;
        int pos = 0;
        for(int j = 0; j < s.length(); j++) if(s[j] == '*') pos = j;
        for(int j = 0; j < 26; j++){
            s[pos] = (char)(j + 'a');
            Trie::insert(s);
        }
    }
    Trie::clc(c+1);
    Trie::find_max(1, 1);
    Trie::get();
    cout << Trie::ans << " " << Trie::maxx << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

赛事出现了若干傻逼错误没过，赛后过了

首先将每个三角形视为单点，三角形有临边的则两点间连边，如此建图。

然后发现只有度$\le 2$的才对答案有贡献，并且剩下的节点的选择方案就是“没有上司的舞会”的思路(队友想的，非常牛逼)。

然后实现即可。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
#define double long double
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;
int n,cnt;
struct point{
    int x,y;
    bool operator<(const point &t)const {
        return x<t.x||x==t.x&&y<t.y;
    }
    bool operator==(const point &t)const {
        return x==t.x&&y==t.y;
    }
};
struct node{
    point a,b;
    double dis(){ 
        return sqrtl(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y)); 
    }
    bool operator<(const node &t)const {
        return a<t.a||a==t.a&&b<t.b;
    }
};

point minn(point x,point y){
    if(x.x<y.x||x.x==y.x&&x.y<y.y)return x;
    return y;
}
point maxx(point x,point y){
    if(x.x>y.x||x.x==y.x&&x.y>y.y)return x;
    return y;
}
map<node,int>mp;
vector<int>p[200005];
const double inf =1e18; 
double ww[N];
double dp[N][2];
void dfs(int u,int fa){
    for(auto v:p[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    dp[u][1]=ww[u];
    for(auto v:p[u]){
        if(v==fa)continue;
        dp[u][1]+=min(dp[v][0],dp[v][1]);
    }
    if(p[u].size()<=2){
        dp[u][0]=inf;
    }
    else{
        for(auto v:p[u]){
            if(v==fa)continue;
            dp[u][0]+=dp[v][1];
        }
    }
}

inline void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        point q,w,e;
        cin>>q.x >> q.y >> w.x >> w.y >> e.x >> e.y;
        node edge1={minn(q, w), maxx(q, w)};
        node edge2={minn(e, w), maxx(e, w)};
        node edge3={minn(e, q), maxx(q, e)};
        if(mp.count(edge1)){
            p[mp[edge1]].emplace_back(i);
            p[i].emplace_back(mp[edge1]);
        }
        if(mp.count(edge2)){
            p[mp[edge2]].emplace_back(i);
            p[i].emplace_back(mp[edge2]);
        }
        if(mp.count(edge3)){
            p[mp[edge3]].emplace_back(i);
            p[i].emplace_back(mp[edge3]);
        }
        double d1=edge1.dis(),d2=edge2.dis(),d3=edge3.dis();
        double d4=(d1+d2+d3)/2;
        ww[i]=sqrtl(d4*(d4-d1)*(d4-d2)*(d4-d3));
        mp[edge1] = i;
        mp[edge2] = i;
        mp[edge3] = i;
    }
    dfs(1,0);
    cout<<min(dp[1][0],dp[1][1]);
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(1);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

队友做的，跑了一遍SCC_Tarjan然后建新图记录出入度即可。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

int n, m;
int newid[N];
vector<int> p[N];
vector<vector<int>> scc;
int dfn[N], low[N], ins[N], idx, cnt;

vector<int> st, f;

void scc_tarjan(int u){
    low[u] = dfn[u] = ++idx;
    st.emplace_back(u);
    ins[u] = 1;
    for(auto v : p[u]){
        if(!dfn[v]) scc_tarjan(v);
        if(ins[v]) low[u] = min(low[u], low[v]);
    }
    if(low[u] == dfn[u]){
        ++cnt; 
        f.clear();
        while(1){
            int v = st.back(); st.pop_back();
            f.emplace_back(v);
            ins[v] = 0;
            newid[v] = cnt;
            if(u == v) break;
        }
        scc.emplace_back(f);
    }
}
vector<int>g[500005];
int ind[500005],outd[500005];
inline void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        p[u].emplace_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(dfn[i]) continue;
        scc_tarjan(i);
    }
    if(cnt==1){
        cout<<0<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        for(auto v:p[i]){
            if(newid[i]!=newid[v]){
                ind[newid[v]]++;
                outd[newid[i]]++;
            }
        }
    }
    int cnt1=0,cnt2=0;
    for(int i=1;i<=cnt;i++){
        if(ind[i]==0){
            cnt1++;
        }
        if(outd[i]==0)cnt2++;
    }
    
    cout<<max(cnt1,cnt2);
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

签到，判断输入里是否包含9。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;


inline void solve(){
    for(int i = 1; i <= 9; i++){
        int x; cin >> x;
        if(x == 9){ cout << 'F'; return; }
    }
    cout << 'S' << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

23点，写了一发过不去样例，就丢给队友了。然后发现只需要多讨论就可以了

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;
int a[N], b[N];

int mp[N];

inline void solve(){
    int n = 0; cin >> n;
    int cnt1 = 0, cnt2 = 0;
    int x;
    for(int i = 1; i <= 2; i++) cin >> x, mp[x]++, cnt1 += min(x,10ll);
    for(int i = 1; i <= 2; i++) cin >> x, mp[x]++, cnt2 += min(x,10ll);
    for(int i = 1; i <= n; i++){
        int x = 0; cin >> x, mp[x]++;
        cnt1 += min(x,10ll), cnt2 += min(x,10ll);
    }
    // int left = 23 - cnt2;
    // if(mp[left] < 4) cout << left << endl;
    int r=23-cnt2, l=23-cnt1, ans=1e9;
    if(mp[r]<4) ans=r;
    if(l<r)
    {
        for(int i=l+1;i<=r;i++) 
        {
            if(mp[i]<4) ans=min(ans,i);
        }
    }
    if(ans<=10) 
    {
        cout<<ans<<"\n";
    }
    else cout<<"-1\n";
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

队友给了个思路，双倍数组后对$a$求前缀和，然后对$b$求区间前$k$大前缀和，然后加起来即可。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

int a[N],b[N];

namespace PDT{
    #define ls lc[rt]
    #define rs rc[rt]
    
    int tree[N << 5], lc[N << 5], rc[N << 5], root[N], tot, sum[N<<5];

    void update(int &rt, int pre, int l, int r, int pos){
        rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], tree[rt] = tree[pre] + 1, sum[rt] = sum[pre] + pos;
        if(l == r) return;
        int mid = l + r >> 1;
        if(mid >= pos) update(lc[rt], lc[pre], l, mid, pos);
        else update(rc[rt], rc[pre], mid + 1, r, pos);
    }

    int query(int l, int r, int L, int R, int k){
        if(l == r) return l * k;
        int mid = l + r >> 1, res = tree[rc[R]] - tree[rc[L]];
        if(res >= k) return query(mid+1, r, rc[L], rc[R], k);
        else return sum[rc[R]]-sum[rc[L]]+query(l, mid, lc[L], lc[R], k - res);
    }
}

using PDT::update;
using PDT::query;
using PDT::root;
int pre[N],ans,k,l;
inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) {cin >> a[i];a[i+n]=a[i];}
    for(int i = 1; i <= n; i++) {cin >> b[i];b[i+n]=b[i];}
    for(int i = 1; i <= 2*n; i++) update(root[i], root[i - 1], 1, 1e9, b[i]);
    for(int i=1;i<=2*n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    cin>>k>>l;
    for(int i=n-k+1;i<=n+1;i++){
        ans=max(ans,pre[i+k-1]-pre[i-1]+query(1,1e9,root[i-1],root[i+k-1],l));
        //cout<<i<<" "<<query(1,1e9,root[i-1],root[i+k-1],l)<<" "<<pre[i+k-1]-pre[i-1]<<endl;
    }
    cout<<ans;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}