记录一下这个菜鸡在你谷一月比赛中的一些做出来的题。
一： [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
");
else printf("OK
");
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
",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) 的值。
问题就转化为，每次可以修改一个数，问你修改多少次可以使得整个数列变成同一个数。
桶排序统计出现次数最多的整数即可。注意负数的情况要特判掉。
公差最大为 (wover 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
",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
",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
",num);
for(int i = 1; i <= n; i++)
{
if(i >= L && i <= R) printf("%d ",1);
else printf("%d ",0);
}
printf("
");
}
return 0;
}
T2 「EZEC-5」人赢
你有一个数组 (k)，下标为 (1) 到 (n) 。定义 (f(x,y)=egin{cases} min(k_x,k_y) imes (x + y) &x e y \ k_x imes x&x=y end{cases}) .
让你求 (f(x,y)) 的最大值是多少。
我们先扫一遍可以得到 (kx imes x) 的最大值。
然后观察 (x eq y) 的情况，我们可以枚举一下最小值 (k x)，然后求出比它大的数的最远的位置 (y)。
答案就是 $max(kx imes(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
",ans);
return 0;
}
T3: 「EZEC-5」魔法
给你一个序列 (A), 你现在有两个操作。
- 选取 (A) 中一段区间，把这一段区间里面的数全部加 (1),, 花费为 (a)
- 选取 (A) 中一段区间，把这一段区间里面的数全部乘 (2), 花费为 (b)
求最小花费使得存在一个子区间的元素之和不小于 (s) .
两个操作可以看成全局加一和全局乘二。
因为 (s leq 10^9) ，所以操作而最多会被执行 (32) 次。
可以枚举一下操作二的次数 (k)，然后二分操作一的次数。
判断操作一次数是否合法，实际上判断一下是否存在一个区间的最大子段和大于 (Sover 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
",ans);
return 0;
}