NOIP 模拟赛总结
NOIP 模拟赛 4
4.5小时T3写不完！？码力还是不够啊
T1 括号问号
简单DP题，写着写着就出来了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 5e3 + 7;
constexpr int mod = 998244353;int n;
int ans;
int dp[N][N];string s;inline int read() // 不读负数的普通快读
{int k = 0,f = 1;int c = getchar_unlocked();while(c < '0' || c > '9') c = getchar_unlocked();while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + (c ^ 48),c = getchar_unlocked();return k * f;
}inline void write(int x) // 普通快写
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}signed main()
{freopen("bracket.in","r",stdin);freopen("bracket.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;cin >> s;s = ' ' + s;dp[0][0] = 1;for(int i = 1;i <= n;i ++){for(int j = 0;j <= i;j ++){dp[i][j] = dp[i - 1][j];if(s[i] == '(' && j > 0) (dp[i][j] += dp[i - 1][j - 1]) %= mod;if(s[i] == ')') (dp[i][j] += dp[i - 1][j + 1]) %= mod;if(s[i] == '?'){(dp[i][j] += dp[i - 1][j + 1]) %= mod;if(j > 0) (dp[i][j] += dp[i - 1][j - 1]) %= mod;} }}cout << dp[n][0] << '\n';Blue_Archive;
}
T2 狗卡
神秘贪心。
维护一个凸包。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 1.2e6 + 7;
constexpr int M = 6e5 + 7;int n;
int m;
int sm;
int ans;
int top;
int tpp;
int tim;
int k[M];
int stk[N];
int val[N];
int sumk[M];vector<int> sum[M],a[M];struct miku
{int id,l,r,val,len;miku(int Id = 0,int L = 0,int R = 0){if(!Id) return;id = Id,l = L,r = R;val = sum[id][R] - sum[id][L - 1],len = R - L + 1;}friend bool operator<(miku x,miku y){return x.val * y.len < x.len * y.val;}
}sta[N];inline int read()
{int x = 0,f = 1;int c = getchar_unlocked();while(c < '0' || c > '9') f = (c == '-' ? -1 : f),c = getchar_unlocked();while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar_unlocked();return x * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);freopen("dog.in","r",stdin),freopen("dog.out","w",stdout);n = read();m = read();for(int i = 1;i <= n;i ++){k[i] = read();sumk[i] = sumk[i - 1] + k[i];a[i].emplace_back(0);sum[i].emplace_back(0);for(int j = 0,x;j < k[i];j ++){x = read();a[i].emplace_back(x);sum[i].emplace_back(x + sum[i][j]);}top = 0;stk[++ top] = 1;val[1] = sum[i][1];for(int j = 2;j <= k[i];j ++){while(top && (sum[i][j] - val[top]) * (stk[top] - stk[top - 1]) <= (val[top] - val[top - 1]) * (j - stk[top])) top --;stk[++ top] = j;val[top] = sum[i][j];}for(int j = 1;j <= top;j ++) sta[++ tpp] = miku(i,stk[j - 1] + 1,stk[j]);sm += sum[i][k[i]];}sort(sta + 1,sta + tpp + 1);for(int i = 1;i <= tpp;i ++){for(int j = sta[i].l;j <= sta[i].r;j ++){ans += (tim ++) * a[sta[i].id][j];}}write(ans + tim * (m - sm));ent;Blue_Archive;
}
T3：均衡区间
场上没写完，呜呜呜
考虑扫描线，枚举一个端点，求以其为一端的贡献。
发现贡献可以拆分成两部分。
一部分是用单调栈维护比它大或小的数的个数。
发现这样会多算，所以第二部分要斥一下，斥掉以现在枚举点为最近的最值的区间。
神秘 thick：两个单调栈下标取 \(\max\) ，之后的所有值均合法，就是最后的答案。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 1e6 + 7;
constexpr int LG = 21;
constexpr int INF = 1e9;
constexpr int mod = 998244353;int n;
int tpy;
int top1;
int top2;
int a[N];
int ans1[N];
int ans2[N];
int stk1[N];
int stk2[N];inline int read() // 不读负数的普通快读
{int k = 0,f = 1;int c = getchar_unlocked();while(c < '0' || c > '9') c = getchar_unlocked();while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + (c ^ 48),c = getchar_unlocked();return k * f;
}inline void write(int x) // 普通快写
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}signed main()
{freopen("interval.in","r",stdin);freopen("interval.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();tpy = read();for(int i = 1;i <= n;i ++) a[i] = read();if(tpy == 2){for(int i = 1;i <= n;i ++) write(0),con;ent;for(int i = 1;i <= n;i ++) write(0),con;ent;exit(0);}top1 = top2 = 0;for(int i = 1,l,r,ans;i <= n;i ++){l = r = i;while(a[l] == a[r + 1]) r ++;while(top1 && a[stk1[top1]] > a[i]) top1 --;while(top2 && a[stk2[top2]] < a[i]) top2 --;ans = 0;if(top1 && top2){int op = min(stk1[top1],stk2[top2]);int cnt1 = upper_bound(stk1 + 1,stk1 + top1 + 1,op) - stk1 - 1;int cnt2 = upper_bound(stk2 + 1,stk2 + top2 + 1,op) - stk2 - 1;ans = op - cnt1 - cnt2;}for(int j = l;j <= r;j ++){ans2[j] = ans;stk1[++ top1] = j;stk2[++ top2] = j;}i = r;}reverse(a + 1,a + 1 + n);top1 = top2 = 0;for(int i = 1,l,r,ans;i <= n;i ++){l = r = i;while(a[l] == a[r + 1]) r ++;while(top1 && a[stk1[top1]] > a[i]) top1 --;while(top2 && a[stk2[top2]] < a[i]) top2 --;ans = 0;if(top1 && top2){int op = min(stk1[top1],stk2[top2]);int cnt1 = upper_bound(stk1 + 1,stk1 + top1 + 1,op) - stk1 - 1;int cnt2 = upper_bound(stk2 + 1,stk2 + top2 + 1,op) - stk2 - 1;ans = op - cnt1 - cnt2;}for(int j = l;j <= r;j ++){ans1[j] = ans;stk1[++ top1] = j;stk2[++ top2] = j;}i = r;}reverse(ans1 + 1,ans1 + 1 + n);for(int i = 1;i <= n;i ++) write(ans1[i]),con;ent;for(int i = 1;i <= n;i ++) write(ans2[i]),con;ent;Blue_Archive;
}
T4：喵了个喵了个喵
meow~