记录一下这个菜鸡在你谷一月比赛中的一些做出来的题。
一： [Mivik Round] nurture
T1 Get Your Wish
简单 \(bfs\) 一下即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans;
char a[110][110],ch;
int main()
{
scanf("%d%d",&n,&m); cin>>ch;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin>>a[i][j];
}
}
if(ch == '^')
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == 'o')
{
for(int k = 1; k <= i; k++) if(a[k][j] == 'x') ans = 1;
}
}
}
}
if(ch == 'v')
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == 'o')
{
for(int k = i; k <= n; k++) if(a[k][j] == 'x') ans = 1;
}
}
}
}
if(ch == '<')
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == 'o')
{
for(int k = 1; k <= j; k++) if(a[i][k] == 'x') ans = 1;
}
}
}
}
if(ch == '>')
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == 'o')
{
for(int k = j; k <= m; k++) if(a[i][k] == 'x') ans = 1;
}
}
}
}
if(ans == 1) printf("GG\n");
else printf("OK\n");
return 0;
}
T2 Something Comforting
给你一个长度为 \(2n\) 的合法括号序列，问你这个括号序列经过题目中的算法被生成的概率是多少。
首先我们可以观察到总的情况数有 \(C_{2n}^{n}\) 种，即从 \(2n\) 个位置里面选出 \(n\) 个位置来放左括号。
我们把目标括号分成若干段（每个极大的括号组分为一组）
( ( ) )|( ( ) )|( )|( )
可以发现每个括号组只有两种情况：没被反转过和反转过。
那么合法情况数就是 \(2^{k}\) , \(k\) 为分成的组数。 两者相除即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int p = 998244353;
int n,ans,zi = 1,mu = 1,cnt;
char a[500010];
int ksm(int a,int b)
{
int res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
signed main()
{
scanf("%lld",&n); scanf("%s",a+1);
for(int i = 1; i <= 2*n; i++)
{
ans += a[i] == '(' ? 1 : -1;
if(ans == 0) cnt++;
}
for(int i = 1; i <= n; i++) zi = zi * i % p;
for(int i = n+1; i <= 2*n; i++) mu = mu * i % p;
printf("%lld\n",ksm(2,cnt) * zi % p * ksm(mu,p-2) % p);
return 0;
}
其他题不会写，打了个暴力走人了。
实际得分： \(100 + 100 + 10 + 15 = 225\)
二：EA 的练习赛 2
T1: ix35 的等差数列
给定一包含 \(n\) 项的正整数列 \(a_1, a_2, \ldots , a_n\)，满足 \(1 \leq a_i \leq w\)。
现可以进行若干次修改，一次修改可将数列的任意一项修改为任意 \(\leq w\) 的正整数。
求：至少进行多少次修改，才能使得原数列变为一公差为非负整数的等差数列。
赛后被 \(hack\) 到死的一道题。
对于一个等差数列，每个位置可以表示成 \(a_1 + (i-1) * d\) 的形式。
我们先枚举一下公差 \(d\), 然后对于原数列中的第 \(i\) 项，减去 \((i-1)*d\) ,就可以得到合法的 \(a_1\) 的值。
问题就转化为，每次可以修改一个数，问你修改多少次可以使得整个数列变成同一个数。
桶排序统计出现次数最多的整数即可。注意负数的情况要特判掉。
公差最大为 \(w\over n\) ,所以复杂度为 \(O(w+n)\).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3e5+5;
int n,w,ans,a[N],sum[N],tong[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void slove(int d)
{
for(int i = 1; i <= n; i++)
{
sum[i] = a[i] - (i-1) * d;
if(sum[i] >= 0) tong[sum[i]]++;
}
for(int i = 1; i <= n; i++)
{
if(sum[i] >= 0 && sum[i] + (n-1) * d <= w) ans = min(ans,n-tong[sum[i]]);
}
for(int i = 1; i <= n; i++) if(sum[i] >= 0) tong[sum[i]] = 0;
}
int main()
{
n = read(); w = read(); ans = n;
if(n == 1) {printf("%d\n",0); return 0;}
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 0; i <= w/(n-1); i++) slove(i);
printf("%d\n",ans);
return 0;
}//扔一下赛时代码吧，赛后数据可能过不去
之后打了个第三题的暴力就走人了。
实际得分： \(100+0+5+0+0 = 105\)
三： 洛谷 1 月月赛 & EZEC R5
这算是自己打的比较好的一次月赛了。
实际得分： \(100+100+100+5+0+0 = 305\).
T1 「EZEC-5」修改数组
给你一个 \(01\) 序列，每次操作你可以把某一位置的零改为 \(1\), 设操作次数为 \(y\), 修改完之后整个序列的最长的连续的 \(1\) 的字段的长度为 \(x\)，求 \(x-y\) 的最大值。
思维题。显然最大值为序列中 \(1\) 的个数，构造方案找到最左边和最右边的一的位置，然后把这中间的位置赋为一，其他位置赋为 \(0\) 即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf = 1e7+10;
int T,n,L,R,num,x;
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int main()
{
T = read();
while(T--)
{
n = read(); L = inf, R = -inf, num = 0;
for(int i = 1; i <= n; i++)
{
x = read();
if(x == 1)
{
num++;
L = min(L,i);
R = max(R,i);
}
}
printf("%d\n",num);
for(int i = 1; i <= n; i++)
{
if(i >= L && i <= R) printf("%d ",1);
else printf("%d ",0);
}
printf("\n");
}
return 0;
}
T2 「EZEC-5」人赢
你有一个数组 \(k\)，下标为 \(1\) 到 \(n\) 。定义 \(f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}\) .
让你求 \(f(x,y)\) 的最大值是多少。
我们先扫一遍可以得到 \(kx\times x\) 的最大值。
然后观察 \(x\neq y\) 的情况，我们可以枚举一下最小值 \(k x\)，然后求出比它大的数的最远的位置 \(y\)。
答案就是 $max(kx\times(x+y)) $ 。
求比一个数大的数的最远位置，排一下序，维护最右边的位置即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int n,ans,R;
struct node
{
int w,pos;
}e[1000010];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
bool comp(node a,node b)
{
return a.w > b.w;
}
signed main()
{
n = read();
for(int i = 1; i <= n; i++) e[i].w = read(), e[i].pos = i;
for(int i = 1; i <= n; i++) ans = max(ans,e[i].w * i);
sort(e+1,e+n+1,comp);
for(int i = 1; i <= n; i++)
{
ans = max(ans,e[i].w * (R + e[i].pos));
R = max(R,e[i].pos);
}
printf("%lld\n",ans);
return 0;
}
T3: 「EZEC-5」魔法
给你一个序列 \(A\), 你现在有两个操作。
- 选取 \(A\) 中一段区间，把这一段区间里面的数全部加 \(1\),, 花费为 \(a\)
- 选取 \(A\) 中一段区间，把这一段区间里面的数全部乘 \(2\), 花费为 \(b\)
求最小花费使得存在一个子区间的元素之和不小于 \(s\) .
两个操作可以看成全局加一和全局乘二。
因为 \(s \leq 10^9\) ，所以操作而最多会被执行 \(32\) 次。
可以枚举一下操作二的次数 \(k\)，然后二分操作一的次数。
判断操作一次数是否合法，实际上判断一下是否存在一个区间的最大子段和大于 \(S\over 2^k\) 即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,A,B,s,tmp,ans = 1e18;
int a[N],base[50],sum[N],f[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
bool judge(int mid,int maxn)
{
for(int i = 1; i <= n; i++) f[i] = 0;
for(int i = 1; i <= n; i++) sum[i] = a[i] + mid;
int res = sum[1]; f[1] = sum[1];
for(int i = 2; i <= n; i++)
{
if(f[i-1] <= 0) f[i] = sum[i];
else f[i] = f[i-1] + sum[i];
res = max(res,f[i]);
}
return res >= maxn;
}
int slove(int x)
{
if(base[x] >= s) tmp = 1;
else
{
if(s % base[x] != 0) tmp = s / base[x] + 1;
else tmp = s / base[x];
}
int L = 0, R = 1e10, res = 0;
while(L <= R)
{
int mid = (L + R)>>1;
if(judge(mid,tmp))
{
R = mid - 1;
res = mid;
}
else L = mid + 1;
}
return res * A + x * B;
}
signed main()
{
n = read(); A = read(); B = read(); s = read(); base[0] = 1;
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= 30; i++) base[i] = base[i-1] * 2;
for(int i = 0; i <= 30; i++)
{
if(i * B > ans) continue;
ans = min(ans,slove(i));
}
printf("%lld\n",ans);
return 0;
}