周末—FBI_诣起来玩1[BCDEGH]

问题虫洞——B：B - Sport Mafia CodeForces - 1195B

黑洞内窥：

给你N个操作，和剩余的糖果数K， 求你吃了多少个糖果，操作只有两种：

1，你吃掉一个

2，每次增加比之前增加的糖果数多一个，

比如，你前三次都执行2操作， 则你现在有1+2+3 = 6个糖果。

光年之外：

设你吃掉的糖果是B，操作2的数目是A，解方程即可：

AC代码：（记得用long long， 不然会，，凉凉）

//#include<bits/stdc++.h>
#include  <stdio.h>
#include <iostream>
#include<algorithm>
#include      <set>
#include      <map>
#include    <queue>
#include    <stack>
#include   <string>
#include   <math.h>
#include   <vector>
#include  <cstring>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 1000000007;
#define mem(a, b) memset(a, b, sizeof(a))int main()
{ll n, k, a=0, b=0;cin >> n >> k;ll ans = 2*(n+k);for(ll i = sqrt(ans); i>=0; --i){if(i*(i+3) == ans){a = i;break;}}cout << n-a << '\n';return 0;
}

问题虫洞——C：C - Basketball Exercise CodeForces - 1195C

黑洞内窥：

有两排学生，两组序号都是从左到右为1到n，

篮球教练想从中选出一些人来组建出一支身高和最高的队伍，人数不限，

但选人方式有规则，

从左往右选，他不会连续从同一排里选择2个人，

也就是如果上一次选择了学生是第一排的，那么这次就不会在第一排中选，同理第二排也是，而且可以选择不选。

光年之外：

当然，我也看出来是dp了，但是转移方程还是没写出来（原谅我这个蒟蒻吧。。。）

因为在面对序号为i的两个学生的时候，为使在考虑了前i个学生的时候身高和最大，那么要求考虑了前i-1个学生的身高和要是最大的。

如果上一次选择的是第一排的学生，那么这一次只能选择第二排的学生，或者不选。

反过来说就是如果这次要选择第一排的，那么要求面对前i-1人时第二排的答案最优，求解时加上第一排第i个学生的身高，

如果这次要选择不选，那么要求面对前i-1人时第一排的答案最优，否则面对第i个人的时候不是最优解，那么在选择这两种方式的时候选择大的就是这一次的最优解。

同理，第二排也是这样考虑的。两排都同时进行一次DP，最后取两者中大的即可。

AC代码：（记得用long long， 不然会，，凉凉）

#include<bits/stdc++.h>
#include  <stdio.h>
#include <iostream>
#include<algorithm>
#include      <set>
#include      <map>
#include    <queue>
#include    <stack>
#include   <string>
#include   <math.h>
#include   <vector>
#include  <cstring>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 998244353;
#define mem(a, b) memset(a, b, sizeof(a))
typedef unsigned __int64 uint64;ll a[MAXN], b[MAXN];
ll h1[MAXN], h2[MAXN];
int main()
{int n;cin >> n;for(int i=1; i<=n; ++i) scanf("%lld", a+i);for(int i=1; i<=n; ++i) scanf("%lld", b+i);h1[0] = h2[0] = 0;for(int i=1; i<=n; ++i){h1[i] = max(h1[i-1], h2[i-1] + a[i]);h2[i] = max(h2[i-1], h1[i-1] + b[i]);}cout << max(h1[n], h2[n]) << '\n';return 0;
}

问题虫洞——D：D - Submarine in the Rybinsk Sea (easy edition) CodeForces - 1195D1

黑洞内窥：

光年之外：

我的思路：

暴力出n^2个串，然后相加。我当时也想到了每个数在特定位置上的贡献是n次，只不过，我还是暴力了。。。因为我觉得那样子不好算，，，

正确的思路：

我们知道f(ai,?)时ai的贡献，以及f(?,ai)时ai的贡献，分别计算即可。
即，每个第k位（从1开始）都会恰好在2k和2k−1位各贡献n次。

AC代码：

#include<bits/stdc++.h>
#include  <stdio.h>
#include <iostream>
#include<algorithm>
#include      <set>
#include      <map>
#include    <queue>
#include    <stack>
#include   <string>
#include   <math.h>
#include   <vector>
#include  <cstring>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 998244353;
#define mem(a, b) memset(a, b, sizeof(a))
typedef unsigned __int64 uint64;int n;
int a[MAXN];
ll inv(ll x)
{ll ans=0;stack<ll> st;while(x){st.push(x%10);x/=10;}while(!st.empty())//这个栈我觉得用的很好。省事很多{ans = ans*10 + st.top();ans = ans*10 + st.top();st.pop();ans%=mod;}return ans*n%mod;
}int main()
{cin >> n;for(int i=0; i<n; ++i)scanf("%d", a+i);ll sum=0;for(int i=0; i<n; ++i){sum += inv(a[i]);sum %= mod;}cout << sum << '\n';return 0;
}

问题虫洞——E：E - OpenStreetMap CodeForces - 1195E

黑洞内窥：

给你一个nm的矩阵你要求给定矩阵ab的子矩阵的最小值的和，并且给出矩阵各元素的递推公式

光年之外：

对于某一行来说，我们只需要维护[1,b],[2,b+1],[3,b+2]…[m-b+1,m]的最小值，然后再对列进行维护即可，最后的矩阵的和就是答案。

这里，我们用单调栈来维护。

对于某一行，我们维护一个长度最大为b的单调递增栈，每次遇到一个元素则把这个元素放入栈中，同时，栈中比此元素大的数字则会被pop出丢弃掉，最后答案就是栈底元素的值。处理完行之后，再处理每一列即可。这时，c[i][j]的值是以(i,j)为右下角，长宽各为a和b的矩形的最小值。

AC代码：

#include<bits/stdc++.h>
#include  <stdio.h>
#include <iostream>
#include<algorithm>
#include      <set>
#include      <map>
#include    <queue>
#include    <stack>
#include   <string>
#include   <math.h>
#include   <vector>
#include  <cstring>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef long long ll;
#define MAXN 3005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 998244353;
#define mem(a, b) memset(a, b, sizeof(a))
typedef unsigned __int64 uint64;ll n, m, q, e, g, x, y, z;
ll a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
ll arr[MAXN];
int main()
{cin >> n >> m >> q >> e;cin >> g >> x >> y >> z;for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j){a[i][j] = g;g = (g*x%z+y%z)%z;}for(int i=1; i<=n; ++i){int l=1, r=0;for(int j=1; j<=m; ++j){if(l <= r && j-arr[l]+1 > e) ++l;while(l<=r && a[i][j] <= a[i][arr[r]]) --r;arr[++r] = j;b[i][j] = a[i][arr[l]];}}for(int j=1; j<=m; ++j){int l=1, r=0;for(int i=1; i<=n; ++i){if(l<=r && i-arr[l]+1 > q) ++l;while(l<=r && b[i][j]<=b[arr[r]][j]) --r;arr[++r] = i;c[i][j] = b[arr[l]][j];}}ll sum=0;for(int i=q; i<=n; ++i)for(int j=e; j<=m; ++j)sum+=c[i][j];cout << sum << '\n';return 0;
}

问题虫洞——G：G - Convert to Ones CodeForces - 997A

黑洞内窥：

给你一个字符串s，当中只有两种字符 ‘0’ 和 ‘1’，你可选择两种操作。

第一种，选择一个子字符串，将它翻转，如001 翻转变为100

第二种，选择一个子字符串，将字符翻转，如001变为110，就0变1，1变0

第一种操作消耗x元，第二种操作消耗y元，问你最少用多少钱可以将这个字符串全部变为1

光年之外：

其实主要是看x， y的大小，因为这决定你是reverse还是直接置1。

翻转操作实际就是合并两段 0 ，特判全 1 的情况，假设有 k 段 0 ，答案是 (k−1)min(x,y)+y 。

一篇比较容易理解的博客：J - Convert to Ones CodeForces - 997A （思维）

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 998244353;
#define mem(a, b) memset(a, b, sizeof(a))
typedef unsigned __int64 uint64;char s[MAXN*3];
int main()
{ll n, x, y;cin >> n >> x >> y >> s;ll ans = 0, sum;for(int i=0; i<n; ++i){if(s[i] == '0'){while(s[i] == '0' && i < n)++i;ans++;}}if(ans == 0) puts("0");else cout << min(x, y)*(ans-1)+y << '\n';return 0;
}

问题虫洞——H：H - Roman Digits CodeForces - 997B

黑洞内窥：

将1，5，10，50填入n个格子中，相加后的值有多少种情况

光年之外：

打了前30项的表。。。。

然后你就会发现，在第11项之后会成等差数列，公差为49，好了，直接用公式就好了，，，，

AC代码：（记得用long long， 不然会，，凉凉）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll
const ll mod = 1000000007;
#define mem(a, b) memset(a, b, sizeof(a))int a[20];
int main ()
{a[1] = 4;a[2] = 10;a[3] = 20;a[4] = 35;a[5] = 56;a[6] = 83;a[7] = 116;a[8] = 155;a[9] = 198;a[10] = 244;a[11] = 292;ll n, ans;cin >> n;if(n <= 11) ans = a[n];else ans = a[11]+(n-11)*49;cout << ans << '\n';return 0;
}