Codeforces Round #551 (Div. 2)
算是放弃颓废决定好好打比赛好好刷题的开始吧
A. Serval and Bus
处理每个巴士最早到站且大于t的时间
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,t;
int c[105];
void Solve() {
read(N);read(t);
int s,d;
for(int i = 1 ; i <= N ; ++i) {
read(s);read(d);
if(s >= t) c[i] = s;
else c[i] = s + ((t - s - 1) / d + 1) * d;
}
int ans = 1;
for(int i = 2 ; i <= N ; ++i) {
if(c[ans] - t > c[i] - t) ans = i;
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
B. Serval and Toy Bricks
保证有解直接在俯视图每个1的位置填上行列上限的最小值即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M,H;
int f[105],l[105];
void Solve() {
read(N);read(M);read(H);
for(int i = 1 ; i <= M ; ++i) {
read(f[i]);
}
for(int i = 1 ; i <= N ; ++i) {
read(l[i]);
}
int a = 0;
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= M ; ++j) {
read(a);
if(!a) out(0);
else out(min(l[i],f[j]));
space;
}
enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
C. Serval and Parenthesis Sequence
如果每个位置都不合法，只需要左右两端是匹配的括号，然后对于剩下的部分做括号匹配即可
就是从前往后扫，如果遇到左括号扔进一个栈，遇到问号扔到一个栈，遇到右括号优先找一个左括号匹配，然后问好匹配左括号，然后问号两两匹配，不用在乎先后顺序，因为对于一个完整的匹配()，如果我在这个括号里插入一个(，在最右再多一个)，还是一个完整匹配
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
char s[300005];
int N;
int sta[2][300005],top[2];
void Solve() {
read(N);
scanf("%s",s + 1);
if(s[1] == ')' || s[N] == '(') {puts(":(");return;}
if(N & 1) {puts(":(");return;}
s[1] = '(';s[N] = ')';
for(int i = 2 ; i < N ; ++i) {
if(s[i] == '(') sta[0][++top[0]] = i;
else if(s[i] == '?') sta[1][++top[1]] = i;
else {
if(top[0]) --top[0];
else if(top[1]){
int u = sta[1][top[1]--];
s[u] = '(';
}
else {puts(":(");return;}
}
}
while(top[0]) {
int u = sta[1][top[1]--],v = sta[0][top[0]--];
if(u < v) {puts(":(");return;}
s[u] = ')';
}
if(top[1] & 1) {puts(":(");return;}
for(int i = 1 ; i <= top[1] ; ++i) {
int u = sta[1][i];
if(i & 1) s[u] = '(';
else s[u] = ')';
}
for(int i = 1 ; i <= N ; ++i) {
putchar(s[i]);
}
enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
D. Serval and Rooted Tree
我们可以求出每个点最大能取到第几大的
设这个值是\(dp[u]\)
如果一个节点是min，答案就是这个节点所有儿子的dp[u] + 1的总和-1
如果一个节点是max，答案就是这个节点所有儿子中最小的dp[u]
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,op[MAXN],f[MAXN],dp[MAXN],K;
vector<int> son[MAXN];
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) read(op[i]);
for(int i = 2 ; i <= N ; ++i) read(f[i]);
for(int i = N ; i >= 1 ; --i) {
if(son[i].size() == 0) {dp[i] = 0;++K;}
else {
int sum = 0,mm = N;
for(auto s : son[i]) {
mm = min(dp[s],mm);
sum += dp[s] + 1;
}
if(!op[i]) dp[i] = sum - 1;
else dp[i] = mm;
}
son[f[i]].pb(i);
}
out(K - dp[1]);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
E. Serval and Snake
我们直接问每一行或一列（认为是一行的下边界或一列的右边界）的线切开了多少大蛇，如果某一行切开的蛇和上一行切开的蛇相差是奇数，那么这行必定有个头或者有个尾
如果行列都有这样的，那么判断这两行两列交出的四个点哪个点连向四周的边是奇数
如果只有行或列有，那么可以通过二分，就是最小列的使得这一行的切割点是奇数
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int r[1005],c[1005];
vector<int> ac,ar;
vector<pii > ans;
int Query(int x1,int y1,int x2,int y2) {
printf("? %d %d %d %d\n",x1,y1,x2,y2);
fflush(stdout);
int x;read(x);return x;
}
void Solve() {
read(N);
for(int i = 1 ; i < N ; ++i) {
r[i] = Query(1,1,i,N);
c[i] = Query(1,1,N,i);
}
for(int i = 1 ; i <= N ; ++i) {
if((r[i] ^ r[i - 1]) & 1) ar.pb(i);
if((c[i] ^ c[i - 1]) & 1) ac.pb(i);
}
if(ar.size() >= 2 && ac.size() >= 2) {
for(int i = 0 ; i < 2 ; ++i) {
for(int j = 0 ; j < 2 ; ++j) {
if(Query(ar[i],ac[j],ar[i],ac[j]) == 1) ans.pb(mp(ar[i],ac[j]));
}
}
}
else if(ar.size() >= 2) {
int l = 1,r = N;
while(l < r) {
int mid = (l + r) >> 1;
if(Query(ar[0],1,ar[0],mid) & 1) r = mid;
else l = mid + 1;
}
ans.pb(mp(ar[0],l));ans.pb(mp(ar[1],l));
}
else if(ac.size() >= 2) {
int l = 1,r = N;
while(l < r) {
int mid = (l + r) >> 1;
if(Query(1,ac[0],mid,ac[0]) & 1) r = mid;
else l = mid + 1;
}
ans.pb(mp(l,ac[0]));ans.pb(mp(l,ac[1]));
}
putchar('!');space;out(ans[0].fi);space;out(ans[0].se);space;
out(ans[1].fi);space;out(ans[1].se);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
F. Serval and Bonus Problem
老了，这么普通的一道计数都切不动
就是转化成插入一个点，使得这个点至少在k个之间
可以用dp完成，相当于给2*n + 1个点分配身份
就是\(f[i][j][x]\)x为0或1表示有没有插入特殊点，到了第\(i\)个点
然后如果\(j >= k , x = 0\)，那么可以转移\(f[i][j][x] \rightarrow f[i + 1][j][x]\)
或者加上一个新区间\(f[i][j][x] \rightarrow f[i + 1][j + 1][x]\)
或者结束一个区间\(f[i][j][x] \rightarrow f[i + 1][j - 1][x] \times j\)
方案总数是\(\frac{(2n + 1)!}{n!2^{n}}\)因为两个点是等价的就直接除上\(2^n\)，然后n个区间的标号是没有顺序的，所以再除上一个\(n!\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 998244353;
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void update(int &x,int y) {
x = inc(x,y);
}
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
int k,n,l;
int dp[4005][2005][2],fac[4005];
void Solve() {
read(n);read(k);read(l);
dp[0][0][0] = 1;
for(int i = 0 ; i < 2 * n + 1; ++i) {
for(int j = 0 ; j <= n ; ++j) {
for(int x = 0 ; x <= 1 ; ++x) {
if(!dp[i][j][x]) continue;
if(j >= k && !x) update(dp[i + 1][j][1],dp[i][j][x]);
if(j >= 1) update(dp[i + 1][j - 1][x],mul(dp[i][j][x],j));
update(dp[i + 1][j + 1][x],dp[i][j][x]);
}
}
}
fac[0] = 1;
for(int i = 1 ; i <= 2 * n + 1 ; ++i) fac[i] = mul(fac[i - 1],i);
int ans = l;
ans = mul(ans,dp[2 * n + 1][0][1]);
ans = mul(ans,fpow(fac[2 * n + 1],MOD - 2));
ans = mul(ans,fac[n]);
ans = mul(ans,fpow(2,n));
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}