FBI_诣起来玩1（单调队列，规律）

D1题Submarine in the Rybinsk Sea CodeForces - 1195D1

题意：给定f(x,y)的构造方式：

然后让我们计算。

分析 我们可以考虑一下两个数的情况 123 和 234.

结果为112233 + 223344 + 122334 + 213243的和。即每个数的各个位都在间隔位上做出了两次贡献即123 中的1在100000和010000中都做出了两次贡献。

AC代码：

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll unsigned long long
const ll mod = 998244353;
const int maxn = 1e5 + 10;int k, n;
ll dp[maxn][2], a[maxn], b[maxn];
string str[maxn];
ll ct(ll a)
{stack<ll> st;while(a){st.push(a % 10);a /= 10;}ll ans = 0;while(!st.empty()){ans = ans * 10 + st.top();ans = ans * 10 + st.top();st.pop();}return ans % mod * n % mod;
}
int main()
{//cout << ct("111", "2222") << endl;std::ios::sync_with_stdio(false);while(cin >> n){ll ans = 0, d;for(int i = 0; i < n; i++){cin >> d;ans += ct(d);ans %= mod;}cout << ans << endl;}return 0;
}

E - OpenStreetMap CodeForces - 1195E （单调队列）

题意：给你一定的规则让你构造出一个m * n 的矩阵， 然后让你求得是所有a * b矩阵的最小值。

分析：这题应该是这场中最值得补的一道题，

如图所示只要i和j均大于了a,b之后每走一步都会有一个最小值。然后你可以发现这题可以用单调队列来做，即先维护1 * b的矩阵，单调队列区间维护长为b区间内的最小值。然后再相同的维护在1*b基础上1*a的最小值，这样一来我们就可以得到a * b的最小值。

单调队列模板

for(int i = 1; i <= n; i++)
{while(!pre.empty()) pre.pop_back();for(int j = 1; j <= m; j++){while(!pre.empty() && pre.front() <= j - b) pre.pop_front(); // 超出区间的不再计算从前部出队列while(!pre.empty() && h[i][pre.back()] >= h[i][j]) pre.pop_back(); // 维护的是单调减pre.push_back(j);minn[i][j] = h[i][pre.front()];}
}

AC代码：

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
const int maxn = 3010;int n, m, a, b;
ll g[maxn * maxn], x, y, z;
ll h[maxn][maxn], minn[maxn][maxn];
deque<ll> pre;
int main()
{while(~scanf("%d%d%d%d", &n, &m, &a, &b)){scanf("%lld%lld%lld%lld", &g[0], &x, &y, &z);for(int i = 1; i < maxn * maxn; i++)g[i] = (g[i - 1] *x + y) % z;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++)h[i][j] = g[(i - 1) * m + j - 1];}ll ans = 0;while(!pre.empty()) pre.pop_back();for(int i = 1; i <= n; i++){while(!pre.empty()) pre.pop_back();for(int j = 1; j <= m; j++){while(!pre.empty() && pre.front() <= j - b) pre.pop_front();while(!pre.empty() && h[i][pre.back()] >= h[i][j]) pre.pop_back();pre.push_back(j);minn[i][j] = h[i][pre.front()];}}while(!pre.empty()) pre.pop_back();for(int j = 1; j <= m; j++){while(!pre.empty()) pre.pop_back();for(int i = 1; i <= n; i++){while(!pre.empty() && pre.front() <= i - a) pre.pop_front();while(!pre.empty() && minn[pre.back()][j] >= minn[i][j]) pre.pop_back();pre.push_back(i);if(i >= a && j >= b) ans += minn[pre.front()][j];}}printf("%lld\n", ans);}return 0;
}

G - Convert to Ones CodeForces - 997A（规律题）

题意 给定只含有0和1的字符串然后让你某一串翻转或者0 ->1 ,1->0得到全一的序列求一下最小花费。

分析：010101

两种解决方法：（1）只使用置换1->0, 0->1大约使用num次num为0的块数。

（2）先翻转成一堆再置换一次，当右边是0左边是一的时候就不断翻转，花费(num-1) * x + y

第一种花费 num * y  （2） (num - 1) * x + y

当x < y时第二种更优反之第一种更优。

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
const int maxn = 301000;ll n, x, y;
char ch[maxn];int main()
{scanf("%lld%lld%lld", &n, &x, &y);scanf("%s", ch);int len = strlen(ch);ll sum = 0;int flag = 0, num = 0, cnt = 0;for(int i = 0; i < len; i++){if(ch[i] == '0') flag = 1;else{if(flag) num++;flag = 0;}if(i == len - 1 && flag) num++;}if(num == 0){printf("0\n");return 0;}if(x >= y) printf("%lld\n", 1ll * num * y);else printf("%lld\n", 1ll * (num - 1) * x + y);return 0;
}