人生第一场Div. 1
结果因为想D想太久不晓得Floyd判环法、C不会拆点、E想了个奇奇怪怪的set+堆+一堆乱七八糟的标记的贼难写的做法滚粗了qwq靠手速上分qwqqq
将行列各自离散化并记录下每一个值在行离散化时和列离散化时得到的值以及每一行、每一列出现的最大离散化值
对于每一行和每一列考虑其相交格子的两个离散化值，如果它们的差为\(\Delta\)，就把它对应行列最大离散化值中较小的+\(\Delta\)，最后两者取Max
#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c)){
if(c == '-') f = 1;
c = getchar();
}
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return f ? -a : a;
}
#define PII pair < int , int >
int num[1007][1007] , h[1007][1007] , l[1007][1007] , N , M;
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
N = read(); M = read();
for(int i= 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j)
num[i][j] = read();
vector < PII > vec;
for(int i = 1 ; i <= N ; ++i){
vec.clear();
for(int j = 1 ; j <= M ; ++j)
vec.push_back(PII(num[i][j] , j));
sort(vec.begin() , vec.end());
int pre = 0 , cnt = 0;
for(auto t : vec){
cnt += pre != t.first;
h[i][t.second] = cnt;
pre = t.first;
}
h[i][0] = cnt;
}
for(int i = 1 ; i <= M ; ++i){
vec.clear();
for(int j = 1 ; j <= N ; ++j)
vec.push_back(PII(num[j][i] , j));
sort(vec.begin() , vec.end());
int pre = 0 , cnt = 0;
for(auto t : vec){
cnt += pre != t.first;
l[t.second][i] = cnt;
pre = t.first;
}
l[0][i] = cnt;
}
for(int i = 1 ; i <= N ; ++i){
for(int j = 1 ; j <= M ; ++j)
cout << max(h[i][0] + max(h[i][j] , l[i][j]) - h[i][j] , l[0][j] + max(h[i][j] , l[i][j]) - l[i][j]) << ' ';
cout << endl;
}
return 0;
}KMP求出最长Border，因为最长的Border是两个串拼在一起时能够节约的最长的串。然后能放即放，最后剩下的乱放
#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
char s[500007] , t[500007];
int nxt[500007];
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
scanf("%s %s" , s + 1 , t + 1);
int lS = strlen(s + 1) , lT = strlen(t + 1);
nxt[0] = -1;
for(int i = 1 ; i <= lT ; ++i){
int cur = nxt[i - 1];
while(cur != -1 && t[cur + 1] != t[i])
cur = nxt[cur];
nxt[i] = cur + 1;
}
int cntS0 = 0 , cntS1 = 0 , cntT0 = 0 , cntT1 = 0 , cntCir0 = 0 , cntCir1 = 0;
for(int i = 1 ; i <= lS ; ++i)
if(s[i] == '0') ++cntS0;
else ++cntS1;
for(int i = 1 ; i <= nxt[lT] ; ++i)
if(t[i] == '0') ++cntT0;
else ++cntT1;
for(int i = nxt[lT] + 1 ; i <= lT ; ++i)
if(t[i] == '0') ++cntCir0;
else ++cntCir1;
if(cntS0 >= cntT0 && cntS1 >= cntT1){
cntS0 -= cntT0; cntS1 -= cntT1;
for(int i = 1 ; i <= nxt[lT] ; ++i)
putchar(t[i]);
}
while(cntS0 >= cntCir0 && cntS1 >= cntCir1){
cntS0 -= cntCir0; cntS1 -= cntCir1;
for(int i = nxt[lT] + 1 ; i <= lT ; ++i)
putchar(t[i]);
}
while(cntS0){putchar('0'); --cntS0;}
while(cntS1){putchar('1'); --cntS1;}
return 0;
}PS：在status->execution time->最后一板可以看到我3993ms的好成绩qwq
拆点，对于一个点\(u\)拆成\(d\)个点\(u_0,u_1,...,u_{d-1}\)，对于一条边\((u,v)\)拆成\(d\)条边\((u_i,v_{(i+1) \mod d})\)，然后tarjan求SCC并顺带求出一个SCC中能够到达的博物馆数量，那么也就是要求选择一条从\(1_0\)所在的SCC开始的路径，使得经过的所有点能够到达的博物馆数量最多。在DAG上记搜一下即可。
注意：DAG上的路径的博物馆数量就是所有点的博物馆数量相加，而且不会重复计算博物馆。因为如果存在路径\((u_i,u_j)\)，那么从\(u_j\)沿着与这条路径相同的路径绕\(d-1\)轮肯定会到达\(u_i\)，所以会存在路径\((u_j,u_i)\)，所以对于\(\forall i , j\)，\(u_i\)和\(u_j\)不会存在拓扑先后顺序的关系，所以不会算重。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
#define id(i,j) ((i - 1) * D + j)
const int MAXN = (1e5 + 1) * 50;
vector < int > ch[MAXN];
struct Edge{
int end , upEd;
}Ed[MAXN];
int head[MAXN] , dfn[MAXN] , low[MAXN] , stk[MAXN] , sum[MAXN] , in[MAXN] , ans[MAXN];
int cntEd , top , N , M , D , ts , cntSCC;
bool vis[MAXN] , ins[MAXN] , open[MAXN] , mrk[100003];
inline void addEd(int a , int b){
Ed[++cntEd] = (Edge){b , head[a]};
head[a] = cntEd;
}
void pop(int x){
++cntSCC;
vector < int > nd;
do{
int t = stk[top];
nd.push_back(t / D);
ins[t] = 0; in[t] = cntSCC;
if(!mrk[t / D] && open[t]){
mrk[t / D] = 1;
++sum[cntSCC];
}
}while(stk[top--] != x);
for(auto t : nd) mrk[t] = 0;
}
void tarjan(int x){
dfn[x] = low[x] = ++ts;
vis[x] = ins[x] = 1;
stk[++top] = x;
for(int i = head[x] ; i ; i = Ed[i].upEd){
if(!vis[Ed[i].end]) tarjan(Ed[i].end);
else if(!ins[Ed[i].end]) continue;
low[x] = min(low[x] , low[Ed[i].end]);
}
if(dfn[x] == low[x]) pop(x);
}
int dfs(int x){
if(ans[x] != -1) return ans[x];
ans[x] = 0;
for(auto t : ch[x]) ans[x] = max(ans[x] , dfs(t));
return ans[x] += sum[x];
}
inline char getc(){
char c = getchar();
while(!isdigit(c)) c = getchar();
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
memset(ans , -1 , sizeof(ans));
N = read(); M = read(); D = read();
for(int i = 1 ; i <= M ; ++i){
int a = read() , b = read();
for(int j = 0 ; j < D ; ++j)
addEd(id(a , j) , id(b , (j + 1) % D));
}
for(int i = 1 ; i <= N ; ++i)
for(int j = 0 ; j < D ; ++j)
open[id(i , j)] = getc() - '0';
tarjan(0);
for(int i = 0 ; i <= id(N , (D - 1)) ; ++i)
if(in[i])
for(int j = head[i] ; j ; j = Ed[j].upEd)
if(in[Ed[j].end] && in[i] != in[Ed[j].end])
ch[in[i]].push_back(in[Ed[j].end]);
cout << dfs(in[0]) << endl;
return 0;
}先使用Floyd判环法：找两个人，一个人走一步、一个人走两步，不断走直到这两个人在同一个点。假设其中一个人走了\(x + t\)步，另一个人走了\(2x + 2t\)步，然后再所有人一起走，至多\(3x + 3t\)步所有人就会走到一起。而在这之前肯定会有一段时间所有人已经到达同一个点，只是在环上走，所以当所有人第一次相遇的时候就刚好同时到达终点。
考虑步数，有\(t+x \equiv 2t + 2x \mod c\)，即\(x + t \equiv 0 \mod c\)，即\(x = c - t \mod c\)。所以前两个人的总步数为\(2(c - t \ mod c) + 2t \leq 2t + 2c\)步，最后所有人一起走要走\(t\)步，所以总共要走\(3t+2c\)步。
#include<bits/stdc++.h>
using namespace std;
int get(){
int x;
string s;
cin >> x;
for(int i = 1 ; i <= x ; ++i) cin >> s;
return x;
}
int main(){
do{
puts("next 0 1");
get();
puts("next 1");
}while(get() > 2);
do{
puts("next 0 1 2 3 4 5 6 7 8 9");
}while(get() > 1);
puts("done");
return 0;
}注意到一次性加一段\(0\)的操作只有最前面的\(0\)会产生贡献
对于\(1\ k\)的情况，相当于之前所有的数都不可能会产生贡献
对于其他情况，记录当前所有一次函数的和，将\((i,a_i)\)看做平面上的一个点，那么会产生贡献的点只会出现在所有点的右上凸包上，使用单调栈维护。
#include<iostream>
#include<cstdio>
#include<queue>
#include<set>
//This code is written by Itst
using namespace std;
#define int long long
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
const int MAXN = 3e5 + 7;
#define ld long double
#define PII pair < int , int >
#define st first
#define nd second
PII st[MAXN];
int K , B , top , all;
ld getK(PII a , PII b){return (b.nd - a.nd) * 1.0 / (a.st - b.st);}
int calc(PII nd){return (nd.st - 1) * K + nd.nd + B;}
signed main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
all = read(); st[top = 1] = PII(1 , 0);
for(int M = read() ; M ; --M){
int tp = read();
if(tp == 1){st[top = 1] = PII(1 , 0); B = K = 0; all += read();}
else
if(tp == 2){
PII now = PII(all + 1 , -calc(PII(all + 1 , 0)));
while(top > 1 && getK(now , st[top]) >= getK(st[top] , st[top - 1]))
--top;
st[++top] = now;
all += read();
}
else{B += read(); K += read();}
while(top > 1 && calc(st[top]) >= calc(st[top - 1])) --top;
cout << st[top].st << ' ' << calc(st[top]) << endl;
}
return 0;
}buhui
Codeforces Round #545 (Div. 1) Solution
原文：https://www.cnblogs.com/Itst/p/10513777.html