1000-1009
1000A+B Problem
这个还要写？？？
1001 狼抓兔子
平面图最小割转化为对偶图最短路
#include<bits/stdc++.h>
#define id(i , j , k) ((k) * (N - 1) * (M - 1) + ((i) - 1) * (M - 1) + (j))
#define PII pair < int , int >
#define st first
#define nd second
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c) && c != EOF)
c = getchar();
if(c == EOF)
exit();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
;
struct Edge{
int end , upEd , w;
}Ed[MAXN << ];
int head[MAXN] , dis[MAXN] , N , M , S , T , cntEd;
priority_queue < PII > q;
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void input(){
N = read();
M = read();
T = id(N - , M - , ) + ;
int k;
|| N == ){
int lMin = 0x7fffffff;
; i < max(N , M) ; ++i)
lMin = min(lMin , read());
cout << lMin;
exit();
}
; i <= N ; ++i)
; j < M ; ++j){
k = read();
)
addEd(S , id(i , j , ) , k);
else
if(i == N)
addEd(id(i - , j , ) , T , k);
else{
addEd(id(i - , j , ) , id(i , j , ) , k);
addEd(id(i , j , ) , id(i - , j , ) , k);
}
}
; i < N ; ++i)
; j <= M ; ++j){
k = read();
)
addEd(id(i , j , ) , T , k);
else
if(j == M)
addEd(S , id(i , j - , ) , k);
else{
addEd(id(i , j , ) , id(i , j - , ) , k);
addEd(id(i , j - , ) , id(i , j , ) , k);
}
}
; i < N ; ++i)
; j < M ; ++j){
k = read();
addEd(id(i , j , ) , id(i , j , ) , k);
addEd(id(i , j , ) , id(i , j , ) , k);
}
}
void Dijk(){
memset(dis , 0x3f , sizeof(dis));
dis[S] = ;
q.push(PII( , S));
while(!q.empty()){
PII t = q.top();
q.pop();
if(-t.st > dis[t.nd])
continue;
if(t.nd == T)
return;
for(int i = head[t.nd] ; i ; i = Ed[i].upEd)
if(dis[Ed[i].end] > dis[t.nd] + Ed[i].w){
dis[Ed[i].end] = dis[t.nd] + Ed[i].w;
q.push(PII(-dis[Ed[i].end] , Ed[i].end));
}
}
}
void work(){
Dijk();
cout << dis[T];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
input();
work();
;
}
1001 狼抓兔子
1002 轮状病毒
虽然下面的代码是瞪眼写法，但是这里写一个正经的DP写法
设$f_i$为周围有$i$个点时的方案数。考虑断环成链，强制令第$1$个点与第$i$个点不连通，考虑枚举第$1$个点所在联通块的大小，可以得到状态转移方程：$f_i = \sum\limits_{j = 1}^{i} f_{i-j} \times j$，后面的乘$j$表示中心点有$j$种向这个联通块加边的方式。然后考虑$1$与$n$相连的情况，同样考虑$1$和$n$所在联通块的大小。如果联通块大小为$j$，则有$j-1$种方式使得$1$与$n$是相连的，那么就会有$f_i=\sum\limits_{j = 1}^{i} f_{i-j} \times j+\sum\limits_{j = 2}^{i} f_{i-j} \times j \times (j-1)$
至于下面Code，它表示点为$N$时答案是第一项为$1$、第二项为$3$，递推式为Fibonacci递推式的第$N$项的答案的平方，如果N为偶数，则答案-4。
#include<bits/stdc++.h>
using namespace std;
struct BN{
];
BN(){
memset(arr , , sizeof(arr));
}
void operator =(int x){
arr[] = ;
while(x){
arr[++arr[]] = x % ;
x /= ;
}
}
int& operator [](int x){
return arr[x];
}
inline void output(){
] ; i ; i--)
putchar(arr[i] + );
}
BN operator +(BN b){
BN c;
c[] = max(arr[] , b[]);
; i <= c[] ; i++)
){
c[i + ]++;
c[i] -= ;
}
] + ])
c[]++;
return c;
}
BN operator *(BN b){
BN c;
c[] = arr[] + b[] - ;
; i <= arr[] ; i++)
; j <= b[] ; j++)
c[i + j - ] += arr[i] * b[j];
; i <= c[] ; i++)
){
c[i + ] += c[i] / ;
c[i] %= ;
])
c[]++;
}
return c;
}
}ans[];
int main(){
int N;
cin >> N;
ans[] = ;
ans[] = ;
; i <= N ; i++)
ans[i] = ans[i - ] + ans[i - ];
ans[N] = ans[N] * ans[N];
== )
] -= ) < ){
ans[N][] += ;
ans[N][]--;
]])
ans[N][]--;
}
ans[N].output();
;
}
1002 轮状病毒 瞪眼法
1003 物流运输
因为数据范围很小，故考虑预处理每段时间内不改变航线的情况下的最短路，然后直接DP枚举更换最短路的点即可
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
struct Edge{
int end , upEd , len;
}Ed[];
] , minDis[] , minR[][] , dp[] , N , M , K , E , cntEd;
] , no[][];
queue < int > q;
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].len = c;
head[a] = cntEd;
}
inline int SPFA(){
memset(minDis , 0x3f , sizeof(minDis));
minDis[] = ;
q.push();
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(!cannot[Ed[i].end] && minDis[Ed[i].end] > minDis[t] + Ed[i].len){
minDis[Ed[i].end] = minDis[t] + Ed[i].len;
q.push(Ed[i].end);
}
}
return minDis[M];
}
main(){
cin >> N >> M >> K >> E;
; i <= E ; i++){
int a , b , c;
cin >> a >> b >> c;
addEd(a , b , c);
addEd(b , a , c);
}
int Q;
for(cin >> Q ; Q ; Q--){
int a , b , c;
cin >> a >> b >> c;
while(b <= c)
no[b++][a] = ;
}
memset(minR , 0x3f , sizeof(minR));
memset(dp , 0x3f , sizeof(dp));
; i <= N ; i++){
memset(cannot , , sizeof(cannot));
for(int j = i ; j ; j--){
; k <= M ; k++)
cannot[k] |= no[j][k];
int t = SPFA();
if(t == inf)
break;
minR[j][i] = t;
}
}
dp[] = ;
; i <= N ; i++)
; j >= ; j--)
][i] != inf)
dp[i] = min(dp[i] , dp[j] + minR[j + ][i] * (i - j) + K * (bool)j);
cout << dp[N];
;
}
1003 物流运输
1004 Cards
1005 明明的烦恼
高精度是真的恶心……
Purfer序列+组合数
方案是将所有非$-1$的数放入Purfer序列的总方案$\times$Purfer序列中没有填上的位置给所有$-1$的方案$\times$这两种排列合成一个排列的方案
第一个是$\frac{(\sum du_i -1)!}{\prod (du_i - 1)!}$，第二个是$[N - 2 - \sum (du_i - 1)] ^ {\text{-1的个数}}$，第三个是$C_{N-2}^{\sum (du_i - 1)}$
使用质因数分解避免慢到爆炸的高精度除法
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
struct Bignum{
];
int& operator [](int x){return a[x];}
Bignum(){
memset(a , , sizeof(a));
}
Bignum(int b){
memset(a , , sizeof(a));
while(b){
a[++a[]] = b % ;
b /= ;
}
}
Bignum operator =(int b){
return *this = Bignum(b);
}
void input(){
string s;
cin >> s;
a[] = s.size();
; i <= a[] ; ++i)
a[i] = s[s.size() - i] - ';
}
void output(){
])
putchar(');
] ; i ; --i)
putchar(a[i] + ');
putchar('\n');
}
Bignum operator +(Bignum b){
Bignum c;
c[] = max(a[] , b[]);
; i <= c[] ; ++i)
){
c[i] -= ;
++c[i + ];
}
] + ])
++c[];
return c;
}
Bignum operator +=(Bignum b){
return *this = *this + b;
}
Bignum operator -(Bignum b){
Bignum c;
c[] = max(a[] , b[]);
; i <= c[] ; ++i)
){
c[i] += ;
--c[i + ];
}
] && !c[c[]])
--c[];
return c;
}
Bignum operator -=(Bignum b){
return *this = *this - b;
}
Bignum operator *(Bignum b){
])
return b;
Bignum c;
c[] = a[] + b[] - ;
; i <= a[] ; ++i)
; j <= b[] ; ++j)
c[i + j - ] += a[i] * b[j];
; i <= c[] ; ++i)
){
c[i + ] += c[i] / ;
c[i] %= ;
])
++c[];
}
] && !c[c[]])
--c[];
return c;
}
Bignum operator *=(Bignum b){
return *this = *this * b;
}
Bignum operator ^(int a){
Bignum times() , b(*this);
while(a){
)
times *= b;
b *= b;
a >>= ;
}
return times;
}
bool operator >(Bignum b)const{
] > b[])
;
] < b[])
;
] ; i ; --i)
if(a[i] > b[i])
;
else
if(a[i] < b[i])
;
;
}
bool operator >= (Bignum b){
] > b[])
;
] < b[])
;
] ; i ; --i)
if(a[i] > b[i])
;
else
if(a[i] < b[i])
;
;
}
Bignum operator /(Bignum b){
Bignum c , d = *this , e;
c[] = a[] - b[] + ;
] ; i && d[] ; --i){
e = b * (Bignum() ^ (i - ));
; j <= ; ++j)
if(e > d){
c[i] = j - ;
break;
}
else
d -= e;
}
] && !c[c[]])
--c[];
return c;
}
Bignum operator /=(Bignum b){
return *this = *this / b;
}
Bignum operator %(Bignum b){
return *this - *this / b * b;
}
Bignum operator %=(Bignum b){
return *this = *this % b;
}
}all();
] , jc[][] , prime[][] , ans[];
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
N = read();
; i <= N ; ++i){
int t = i;
; j * j <= t ; ++j)
){
t /= j;
++prime[i][j];
}
)
++prime[i][t];
}
; i <= N - ; ++i)
; j <= i ; ++j)
jc[i][j] = jc[i - ][j] + prime[i][j];
; i <= N ; ++i){
int a = read();
){
){
puts(");
;
}
du[++cnt] = a;
}
}
;
; i <= cnt ; ++i)
sum += du[i] - ;
){
puts(");
;
}
memcpy(ans , jc[sum] , sizeof(ans));
; i <= cnt ; ++i)
; j < du[i] ; ++j)
ans[j] -= jc[du[i] - ][j];
; i <= N - cnt ; ++i)
ans[i] += prime[N - cnt][i] * (N - - sum);
; i <= N - ; ++i)
ans[i] = ans[i] + jc[N - ][i] - jc[sum][i] - jc[N - - sum][i];
; i <= N ; ++i)
all *= Bignum(i) ^ ans[i];
all.output();
;
}
1005 明明的烦恼
1006 神奇的国度
弦图最小染色，详细做法请见CDQ论文（因为我也不会
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
deque < int > num[MAXN];
struct Edge{
int end , upEd;
}Ed[MAXN * ];
int head[MAXN] , ans[MAXN] , cnt[MAXN] , mex[MAXN] , col[MAXN] , N , M , cntEd;
bool vis[MAXN];
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void calc(){
; i <= N ; ++i)
num[].push_back(i);
;
for(int i = N ; i ; --i){
;
while(!cur){
while(!cur && !num[best].empty()){
if(!vis[num[best].back()])
cur = num[best].back();
num[best].pop_back();
}
if(!cur)
--best;
}
vis[cur] = ;
ans[i] = cur;
for(int j = head[cur] ; j ; j = Ed[j].upEd)
if(!vis[Ed[j].end]){
++cnt[Ed[j].end];
num[cnt[Ed[j].end]].push_back(Ed[j].end);
best = max(best , cnt[Ed[j].end]);
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
M = read();
; i <= M ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
calc();
;
for(int i = N ; i ; --i){
for(int j = head[ans[i]] ; j ; j = Ed[j].upEd)
mex[col[Ed[j].end]] = i;
col[ans[i]] = ;
while(mex[col[ans[i]]] == i)
++col[ans[i]];
all = max(all , col[ans[i]]);
}
cout << all;
;
}
1006 神奇的国度
1007 水平可见直线
建立一个上凸包，将斜率从小到大排序，用单调栈维护，半平面交判断无用直线
#include<bits/stdc++.h>
#define ld long double
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct L{
int A , B , ind;
bool operator <(const L a)const{
return A == a.A ? B > a.B : A < a.A;
}
}line[MAXN];
int St[MAXN] , top , N;
inline int sgn(int x){
? - : (x == ? : );
}
inline bool cmp(int a , int b , int c){
int p = line[a].B - line[b].B , q = line[b].A - line[a].A , m = line[b].B - line[c].B , n = line[c].A - line[b].A;
return 1ll * p * n * sgn(q) * sgn(n) >= 1ll * q * m * sgn(q) * sgn(n);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
; i <= N ; ++i){
line[i].A = read();
line[i].B = read();
line[i].ind = i;
}
sort(line + , line + N + );
; i <= N ; ++i){
&& line[i].A == line[i - ].A)
continue;
&& cmp(St[top] , St[top - ] , i) && cmp(St[top - ] , i , St[top]))
--top;
St[++top] = i;
}
; i <= top ; ++i)
St[i] = line[St[i]].ind;
sort(St + , St + top + );
; i <= top ; ++i)
printf("%d " , St[i]);
;
}
1007 水平可见直线
1008 越狱
答案等于$M^N$减去不会产生越狱的方案数，不会越狱的方案数显然是$M \times (M-1)^{N-1}$
#include<bits/stdc++.h>
#define int long long
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
inline int poww(int a , int b){
a %= MOD;
;
while(b){
)
times = times * a % MOD;
a = a * a % MOD;
b >>= ;
}
return times;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
int M = read() , N = read();
cout << (poww(M , N) - M % MOD * poww(M - , N - ) % MOD + MOD) % MOD;
;
}
1008 越狱
1009 GT考试
用$KMP$建立转移矩阵进行矩阵$DP$
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
];
];
struct matrix{
][];
matrix(){memset(a , , sizeof(a));}
int* operator [](int x){return a[x];}
matrix operator *(matrix b){
matrix c;
; i < L ; ++i)
; j < L ; ++j)
; k < L ; ++k)
c[i][j] += a[i][k] * b[k][j];
; i < L ; ++i)
; j < L ; ++j)
c[i][j] %= P;
return c;
}
}S , T;
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
nxt[] = -;
scanf();
S[][] = ;
; i <= L ; ++i){
];
&& s[dir + ] != s[i])
dir = nxt[dir];
nxt[i] = dir + ;
}
; i < L ; ++i){
;
] = {};
){
] - ']){
vis[s[t + ] - ;
--cnt;
)
T[i][t + ] = ;
}
t = nxt[t];
}
T[i][] = cnt;
}
while(N){
)
S = S * T;
T = T * T;
N >>= ;
}
;
; i < L ; ++i)
sum += S[][i];
cout << sum % P;
;
}
1009 GT考试
1010-1019
1010 玩具装箱
斜率优化裸题，见笔记
1011 遥远的行星
对于$i \times A \leq 300$的暴力统计
对于$i \times A > 300$的先暴力统计最后300个，剩下的分块统计
分块统计过程中一段区间$[x,y]$的贡献变为$M_i \times \frac{\sum\limits_{j = x} ^ y M_j}{i - \frac{x + y}{2}}$
#include<bits/stdc++.h>
#define ld long double
//This code is written by Itst
using namespace std;
;
ld M[MAXN] , sum[MAXN] , A;
int N;
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
scanf("%d %Lf" , &N , &A);
; i <= N ; ++i)
scanf("%Lf" , M + i);
; i <= N ; ++i){
sum[i] = sum[i - ] + M[i];
ld ans = ;
int bef = i * A;
, ) ; --j)
ans += M[i] * M[j] / (i - j);
){
bef -= ;
int t = sqrt(bef) , p;
while(bef){
p = max(bef - t , );
ans += M[i] * (sum[bef] - sum[p]) / (i - (bef + p) / );
bef = p;
}
}
printf("%.5Lf\n" , ans);
}
;
}
1011 遥远的行星
1012 最大数
动态开点线段树（当然直接开2e5也是可以的），或者ST表动态统计（ST表不知道比线段树快到哪里去了）
#include<bits/stdc++.h>
using namespace std;
inline unsigned int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
;
] , M , MOD , len , lastans;
inline void insert(int num){
ST[++len][] = num;
; << i <= len ; i++)
ST[len][i] = max(ST[len][i - ] , ST[len - ( << i - )][i - ]);
}
inline int query(int ind){
int l = log2(ind);
<< l)][l]);
}
int main(){
M = read();
MOD = read();
while(M--){
char c = getchar();
while(!isupper(c))
c = getchar();
if(c == 'Q')
printf("%d\n" , lastans = query(read()));
else
insert((read() + lastans) % MOD);
}
;
}
1012 最大数 ST表
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct node{
long long maxN , start , end;
node *left , *right;
node(long long _s , long long _e):start(_s) , end(_e)
{
maxN = ;
if(_e - _s)
{
left = );
right = ) + , _e);
}
}
long long find_max(long long _s, long long _e)
{
if(_s == start && _e == end) return maxN;
) return left->find_max(_s , _e);
) return right->find_max(_s , _e);
) , right->find_max((start + end >> ) + , _e));
}
void change_max(long long k , long long q)
{
maxN = max(maxN , q);
if(start == end) return;
) left->change_max(k , q);
else right->change_max(k , q);
}
};
int main(){
ios::sync_with_stdio();cin.tie();cout.tie();
, cou = ;
cin >> M >> D;
node *Tree = , M);
; i <= M ; i++)
{
char c;
long long a;
cin >> c >> a;
if(c == 'Q'){
;
, cou);
cout << t << endl;
}
else Tree->change_max(++cou , (t + a) % D);
}
;
}
1012 最大数 动态开点线段树
1013 球形空间产生器
将距离公式拆开，将所有二次项与半径的平方合起来看成一个未知数，剩下的圆心$N$维坐标设$N$个未知数，高斯消元即可
#include<bits/stdc++.h>
#define eps 1e-8
using namespace std;
][] , dir[][];
int main(){
int N;
cin >> N;
; i <= N + ; i++){
; j <= N ; j++){
cin >> dir[i][j];
guass[i][j] = * dir[i][j];
guass[i][N + ] += dir[i][j] * dir[i][j];
}
guass[i][N + ] = -;
}
; i <= N + ; i++){
int j;
; j++)
|| guass[j][i] + eps < )
break;
if(j != i)
; k <= N + ; k++)
swap(guass[i][k] , guass[j][k]);
; j >= i ; j--)
guass[i][j] /= guass[i][i];
; j <= N + ; j++)
|| guass[j][i] + eps < ))
; k >= i ; k--)
guass[j][k] -= guass[i][k] * guass[j][i] / guass[i][i];
}
; i <= N ; i++)
cout << ) << guass[i][N + ] << ' ';
;
}
1013 球形空间产生器
1014 火星人
Splay维护字符串Hash，每一次LCQ查询时二分答案
本题及其卡常，请使用较快速的IO并使用自然溢出（要选择较大的质数作为Hash进制位）（话说十年前真是清流竟然不卡自然溢出）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
struct node{
] , fa , size;
char c;
unsigned ll Hash;
}Tree[MAXN];
unsigned ll poww[MAXN] = {};
, root = , N;
inline bool son(int dir){
] == dir;
}
inline void pushup(int dir){
Tree[dir].size = Tree[Tree[dir].ch[]].size + Tree[Tree[dir].ch[]].size + ;
Tree[dir].Hash = Tree[Tree[dir].ch[]].Hash + poww[Tree[Tree[dir].ch[]].size] * Tree[dir].c + poww[Tree[Tree[dir].ch[]].size + ] * Tree[Tree[dir].ch[]].Hash;
}
inline void ZigZag(int dir){
bool f = son(dir);
int t = Tree[Tree[dir].fa].fa;
if(Tree[dir].fa == root)
root = dir;
Tree[Tree[dir].fa].ch[f] = Tree[dir].ch[f ^ ];
Tree[Tree[dir].ch[f ^ ]].fa = Tree[dir].fa;
Tree[t].ch[son(Tree[dir].fa)] = dir;
Tree[Tree[dir].fa].fa = dir;
Tree[dir].ch[f ^ ] = Tree[dir].fa;
Tree[dir].fa = t;
pushup(Tree[dir].ch[f ^ ]);
pushup(dir);
}
inline void Splay(int dir , int fa){
while(Tree[dir].fa != fa)
if(Tree[Tree[dir].fa].fa == fa)
ZigZag(dir);
else{
if(son(dir) == son(Tree[dir].fa))
ZigZag(Tree[dir].fa);
else
ZigZag(dir);
ZigZag(dir);
}
}
void insert(int &now , int size , char c , int fa){
){
now = ++cntNode;
Tree[now].fa = fa;
Tree[now].c = c - 'a';
Splay(now , );
return;
}
]].size + )
insert(Tree[now].ch[] , size - Tree[Tree[now].ch[]].size - , c , now);
else
insert(Tree[now].ch[] , size , c , now);
}
void getKth(int &now , int size , int to){
]].size + == size){
Splay(now , to);
return;
}
]].size)
getKth(Tree[now].ch[] , size - Tree[Tree[now].ch[]].size - , to);
else
getKth(Tree[now].ch[] , size , to);
}
inline bool check(int fir , int sec , int len){
getKth(root , fir , );
getKth(root , fir + len + , root);
unsigned ll t = Tree[Tree[Tree[root].ch[]].ch[]].Hash;
getKth(root , sec , );
getKth(root , sec + len + , root);
]].ch[]].Hash;
}
inline int getAns(int fir , int sec){
if(fir > sec)
swap(fir , sec);
, r = cntNode - sec - ;
while(l < r){
>> ;
if(check(fir , sec , mid))
l = mid;
else
r = mid - ;
}
return l;
}
];
int main(){
; i <= ; i++)
poww[i] = poww[i - ] * ;
scanf("%s" , s);
Tree[].fa = ;
Tree[].ch[] = ;
Tree[].size = ;
Tree[].size = ;
int len = strlen(s);
; i < len ; i++){
insert(root , i + , s[i] , );
Splay(rand() % cntNode + , );
}
int Q;
for(Q = read() ; Q ; Q--){
char c = getchar();
int a;
while(!isupper(c))
c = getchar();
a = read();
switch(c){
case 'Q':
printf("%d\n" , getAns(a , read()));
break;
case 'R':
c = getchar();
while(!islower(c))
c = getchar();
getKth(root , a + , );
Tree[root].c = c - 'a';
pushup(root);
break;
case 'I':
c = getchar();
while(!islower(c))
c = getchar();
insert(root , a + , c , );
}
}
;
}
1014 火星人
1015 星球大战
删边维护并查集显然是不现实的，不过反过来从后往前考虑就是不断加边的过程，并查集就可以实现了。
PS：cout真心慢qwq
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
;
struct Edge{
int start , end , time;
}now[MAXN];
] , times[MAXN << ] , N , M;
int find(int x){
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
bool cmp(Edge a , Edge b){
return a.time < b.time;
}
int main(){
memset(times , 0x3f , sizeof(times));
N = read();
M = read();
; i <= M ; i++){
now[i].start = read();
now[i].end = read();
}
; i < N ; i++)
fa[i] = i;
int K = read();
; i <= K ; i++)
times[read()] = i;
; i <= M ; i++)
now[i].time = min(times[now[i].start] , times[now[i].end]);
sort(now + , now + M + , cmp);
int p = M , cnt = N;
; i--){
while(p && now[p].time > i){
int a = find(now[p].start) , b = find(now[p].end);
if(a != b){
cnt--;
fa[a] = b;
}
p--;
}
ans[i] = cnt;
}
; i <= K ; i++)
printf("%d\n" , ans[i] - i);
;
}
1015 星球大战
1016 最小生成树计数
$Matrix-tree$定理裸题
注意矩阵树定理必须要在原图联通的情况下才能使用，所以每一次计算的时候要把其他的边连上，否则会出现答案为$0$的情况
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
;
struct Edge{
int s , t , w;
bool operator <(const Edge a)const{
return w < a.w;
}
}Ed[];
][] , fa[] , N , M , cntL , ans = ;
map < int , int > lsh;
];
int find(int x){
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
inline int getL(int x){
if(!lsh.count(x))
lsh[x] = ++cntL;
return lsh[x];
}
inline void calc(int x , int y , int &a , int &b , int &c , int &d , int &flg){
a = d = flg = ;
c = b = ;
while(y){
int t = x / y;
x -= t * y;
a = (a - t * c % MOD + MOD) % MOD;
b = (b - t * d % MOD + MOD) % MOD;
swap(x , y);
swap(a , c);
swap(b , d);
flg *= -;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
M = read();
; i <= M ; ++i){
Ed[i].s = read();
Ed[i].t = read();
Ed[i].w = read();
}
; i <= N ; ++i)
fa[i] = i;
sort(Ed + , Ed + M + );
; i <= M ; ++i)
if(fa[find(Ed[i].s)] != fa[find(Ed[i].t)]){
fa[find(Ed[i].s)] = find(Ed[i].t);
vis[i] = ;
}
; i <= N ; ++i)
)){
puts(");
;
}
; i <= M ; ){
int p = i;
cntL = ;
lsh.clear();
memset(mat , , sizeof(mat));
; j <= N ; ++j)
fa[j] = j;
; j <= M ; ++j)
if(vis[j] && Ed[j].w != Ed[i].w)
fa[find(Ed[j].s)] = find(Ed[j].t);
while(p <= M && Ed[i].w == Ed[p].w){
int m = find(Ed[p].s) , n = find(Ed[p].t);
if(m != n){
m = getL(m);
n = getL(n);
--mat[m][n];
--mat[n][m];
++mat[m][m];
++mat[n][n];
}
++p;
}
; j < cntL ; ++j)
; k < cntL ; ++k)
)
mat[j][k] += MOD;
; j < cntL ; ++j)
; k < cntL ; ++k)
if(mat[k][j]){
int a , b , c , d , flg;
calc(mat[j][j] , mat[k][j] , a , b , c , d , flg);
ans = (ans * flg + MOD) % MOD;
for(int l = j ; l < cntL ; ++l){
int r = (mat[j][l] * a + mat[k][l] * b) % MOD;
int s = (mat[j][l] * c + mat[k][l] * d) % MOD;
mat[j][l] = r;
mat[k][l] = s;
}
}
; j < cntL ; ++j)
if(mat[j][j])
ans = (ans * mat[j][j] % MOD + MOD) % MOD;
while(i < p){
fa[find(Ed[i].s)] = find(Ed[i].t);
++i;
}
}
cout << ans << endl;
;
}
1016 最小生成树计数
1018 堵塞的交通
线段树维护列在某一段区间内的矩形的四个顶点之间的连通性，然后大力分类讨论即可
#include<iostream>
#include<cstdio>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return a;
}
;
];
int all;
namespace segTree{
struct node{
bool f1 , f2 , f3 , f4 , f5 , f6;
/*f1: <^ ^>
f2: <v v>
f3: <^
v>
f4: <^
<v
f5: ^>
<v
f6: ^>
v>
*/
node(){f1 = f2 = f3 = f4 = f5 = f6 = ;}
}Tree[MAXN << ];
#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)
node merge(node a , node b , int x){
node t;
t.f4 |= a.f4; t.f6 |= b.f6;
]){
t.f1 |= a.f1 & b.f1; t.f3 |= a.f1 & b.f3;
t.f2 |= a.f5 & b.f3; t.f5 |= a.f5 & b.f1;
}
]){
t.f1 |= a.f3 & b.f5; t.f3 |= a.f3 & b.f2;
t.f2 |= a.f2 & b.f2; t.f5 |= a.f2 & b.f5;
}
] && link[x][]){
t.f4 |= a.f1 & a.f2 & b.f4;
t.f6 |= b.f1 & b.f2 & a.f6;
}
return t;
}
void init(int x , int l , int r){
;
, r);}
}
void modify(int x , int l , int r , int tar , bool flg){
if(l == r){
Tree[x].f3 ^= flg; Tree[x].f4 ^= flg;
Tree[x].f5 ^= flg; Tree[x].f6 ^= flg;
return;
}
if(mid >= tar) modify(lch , l , mid , tar , flg);
, r , tar , flg);
Tree[x] = merge(Tree[lch] , Tree[rch] , mid);
}
node query(int x , int l , int r , int L , int R){
if(L > R) return node();
if(l >= L && r <= R) return Tree[x];
;
node t;
; t = query(lch , l , mid , L , R);}
if(mid < R)
t = f ? merge(t , query(rch , mid + , r , L , R) , mid) : query(rch , mid + , r , L , R);
return t;
}
}
using namespace segTree;
inline char getc(){
char c = getchar();
while(!isupper(c)) c = getchar();
return c;
}
inline void out(bool f){puts(f ? "Y" : "N");}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
init( , , all = read());
char c = getc();
;;
node lft , now , rht;
while(c != 'E'){
if(c == 'A'){
++cntQue;
B = read(); A = read(); D = read(); C = read();
if(A > C){A ^= C ^= A ^= C; B ^= D ^= B ^= D;}
lft = query( , , all , , A - );
rht = query( , , all , C + , all);
now = query( , , all , A , C);
)
)
][] && link[C][] && link[A - ][] && link[C][] && now.f2 && lft.f6 && rht.f4) || (link[A - ][] && link[A - ][] && lft.f6 && now.f5) || (link[C][] && link[C][] && rht.f4 && now.f3));
else
][] && link[A - ][] && lft.f6 && now.f2) || (link[C][] && link[C][] && rht.f4 && now.f1) || (link[A - ][] && link[A - ][] && link[C][] && link[C][] && lft.f6 && rht.f4 && now.f5));
else
)
][] && link[A - ][] && lft.f6 && now.f1) || (link[C][] && link[C][] && rht.f4 && now.f2) || (link[A - ][] && link[A - ][] && link[C][] && link[C][] && lft.f6 && rht.f4 && now.f3));
else
][] && link[A - ][] && link[C][] && link[C][] && now.f1 && lft.f6 && rht.f4) || (link[A - ][] && link[A - ][] && lft.f6 && now.f3) || (link[C][] && link[C][] && rht.f4 && now.f5));
}
else{
B = read(); A = read(); D = read(); C = read();
, , all , A , );
else{
if(A > C) --A;
link[A][B - ] ^= ;
modify( , , all , A , );
}
}
c = getc();
}
;
}
1018 堵塞的交通
1020-1029
1022 小约翰的游戏
Anti-SG模板，先手必胜则有：所有石子为$1$且$SG = 0$或者至少有一堆石子不为$1$且$SG \neq 0$
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
for(int T = read() ; T ; --T){
;
;
for(int N = read() ; N ; --N){
int a = read();
sum ^= a;
flg &= a == ;
}
puts((flg ^ (bool)sum) ? "John" : "Brother");
}
;
}
1022 小约翰的游戏
1023 仙人掌图
1024 生日快乐
爆搜题
#include<bits/stdc++.h>
#define ld long double
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
ld S;
int N;
bool cmp(ld x , ld y){
return x + eps > y && x - eps < y;
}
struct node{
ld x , y;
};
map < node , ld > m;
bool operator <(node a , node b){
return !cmp(a.x , b.x) && a.x < b.x || cmp(a.x , b.x) && a.y < b.y;
}
bool operator ==(node a , node b){
return cmp(a.x , b.x) && cmp(a.y , b.y);
}
ld dfs(int now , ld nowX , ld nowY){
if(m.count((node){nowX , nowY}))
return m[(node){nowX , nowY}];
if(cmp(nowX * nowY , S))
? nowY / nowX : nowX / nowY;
ld ans = 1e18;
; i ; i--){
ld k = dfs(i , nowX / now * i , nowY);
if(k < ans)
ans = min(ans , max(k , dfs(now - i , nowX / now * (now - i) , nowY)));
}
; i ; i--){
ld k = dfs(i , nowX , nowY / now * i);
if(k < ans)
ans = min(ans , max(k , dfs(now - i , nowX , nowY / now * (now - i))));
}
return m[(node){nowX , nowY}] = ans;
}
int main(){
#ifdef BZ
freopen("1024.in" , "r" , stdin);
//freopen("1024.out" , "w" , stdout);
#endif
ld X = read() , Y = read();
N = read();
S = X * Y / N;
printf("%.6Lf" , dfs(N , X , Y));
;
}
1024 生日快乐
1026 Windy数
数位DP裸题（虽然我调了很久，注意边界条件）
#include<bits/stdc++.h>
#define BZ
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
] = {,,,1e3,1e4,1e5,1e6,1e7,1e8,1e9};
][];
inline int abs(int x){
? -x : x;
}
void init(){
; i < ; i++)
dp[][i] = ;
; j <= ; j++)
; k < ; k++)
; l < ; l++)
)
dp[j][k] += dp[j - ][l];
}
int dfs(int now , int pos , int pre){
){
;
; i <= now ; i++)
)
sum++;
return sum;
}
, i;
; poww10[pos] * (i + ) <= now ; i++)
)
sum += dp[pos][i];
)
, i);
else
return sum;
}
inline int work(int pos){
)
;
) + 1e- , sum = ;
; i < t ; i++)
; j <= ; j++)
sum += dp[i][j];
) - dp[t][] + sum;
}
int main(){
#ifdef BZ
freopen("1026.in" , "r" , stdin);
//freopen("1026.out" , "w" , stdout);
#endif
, R = read();
init();
printf("%d" , work(R) - work(L));
;
}
1026 Windy数
1028 麻将
枚举胡的牌，然后枚举对子，接着从左往右更新，能拿三张就拿三张，不能就拿顺子
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
] , forCheck[] , forDui[] , ansNum[] , M;
bool check(int dir){
memcpy(forCheck , pot , sizeof(pot));
forCheck[dir] -= ;
; i <= M ; i++){
)
;
forCheck[i] %= ;
forCheck[i + ] -= forCheck[i];
forCheck[i + ] -= forCheck[i];
}
] == && forCheck[M + ] == ;
}
int main(){
M = read();
int N = read();
; i <= * N + ; i++){
int a = read();
)
forDui[++forDui[]] = a;
}
; i <= M ; i++){
pot[i]++;
)
if(check(i)){
ansNum[++ansNum[]] = i;
pot[i]--;
continue;
}
;
; !f && j <= forDui[] ; j++)
f = check(forDui[j]);
if(f)
ansNum[++ansNum[]] = i;
pot[i]--;
}
])
cout << "NO";
; i <= ansNum[] ; i++)
cout << ansNum[i] << ' ';
;
}
1028 麻将
1029 建筑抢修
有点神仙
按照$T2$从小到大排序，每一个任务尽可能安排在前面，如果存在某个任务没法被放进去就考虑是否能够替换前面时间最长的任务来缩短总任务时间
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
;
priority_queue < int > q;
struct work{
int t1 , t2;
bool operator <(const work a)const{
return t2 == a.t2 ? t1 < a.t1 : t2 < a.t2;
}
}now[MAXN];
int N;
long long all;
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read();
; i <= N ; ++i){
now[i].t1 = read();
now[i].t2 = read();
}
sort(now + , now + N + );
; i <= N ; ++i)
if(all + now[i].t1 <= now[i].t2){
q.push(now[i].t1);
all += now[i].t1;
}
else
if(!q.empty() && now[i].t1 < q.top()){
all = all - q.top() + now[i].t1;
q.pop();
q.push(now[i].t1);
}
cout << q.size();
;
}
1029 建筑抢修
1030-1039
1030 文本生成器
Trie图上DP
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
, MOD = ;
struct node{
] , fail;
bool get;
}Trie[MAXN];
, N , M , dp[][][];
char s[MAXN];
void insert(){
, L = strlen(s + );
; i <= L ; ++i){
if(!Trie[t].ch[s[i] - 'A'])
Trie[t].ch[s[i] - 'A'] = ++cntN;
t = Trie[t].ch[s[i] - 'A'];
}
Trie[t].;
}
void init(){
queue < int > q;
Trie[].fail = ;
; i < ; ++i)
].ch[i]){
Trie[Trie[].ch[i]].fail = ;
q.push(Trie[].ch[i]);
}
else
Trie[].ch[i] = ;
while(!q.empty()){
int t = q.front();
q.pop();
; i < ; ++i)
if(Trie[t].ch[i]){
Trie[Trie[t].ch[i]].fail = Trie[Trie[t].fail].ch[i];
Trie[Trie[t].ch[i]].get |= Trie[Trie[Trie[t].fail].ch[i]].get;
q.push(Trie[t].ch[i]);
}
else
Trie[t].ch[i] = Trie[Trie[t].fail].ch[i];
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read();
M = read();
; i <= N ; ++i){
scanf();
insert();
}
init();
dp[][][] = ;
; i < M ; ++i)
; j <= cntN ; ++j)
; k <= ; ++k)
if(dp[i][j][k])
; p < ; ++p)
(dp[i + ][Trie[j].ch[p]][k | Trie[Trie[j].ch[p]].get] += dp[i][j][k]) %= MOD;
;
; i <= cntN ; ++i)
sum = (sum + dp[M][i][]) % MOD;
cout << sum;
;
}
1030 文本生成器
1031 字符加密
倍长然后SA计算每一个串之间的顺序
#include<bits/stdc++.h>
using namespace std;
;
char s[MAXN];
] , tp[MAXN << ] , pot[MAXN] , sa[MAXN] , h[MAXN];
int maxN , L;
void sort(int p){
memset(pot , , ));
; i <= L ; ++i)
++pot[rk[i]];
; i <= maxN ; ++i)
pot[i] += pot[i - ];
; i <= L ; ++i)
sa[++pot[rk[tp[i]] - ]] = tp[i];
swap(rk , tp);
; i <= L ; ++i)
rk[sa[i]] = rk[sa[i - ]] + (tp[sa[i]] != tp[sa[i - ]] || tp[sa[i] + p] != tp[sa[i - ] + p]);
maxN = rk[sa[L]];
}
int main(){
scanf();
L = strlen(s + );
; i <= L << ; ++i)
s[i] = s[i - L];
s[] = s[L];
L <<= ;
maxN = ;
; i <= L ; ++i){
rk[i] = s[i];
tp[i] = i;
}
sort();
; i <= L && maxN < L ; i <<= ){
;
; j <= i ; ++j)
tp[++cnt] = L - i + j;
; j <= L ; ++j)
if(sa[j] > i)
tp[++cnt] = sa[j] - i;
sort(i);
}
/*for(int i = 1 ; i <= L ; ++i){
if(rk[i] == 1)
continue;
int t = rk[i];
h[t] = max(0 , h[rk[i - 1]] - 1);
while(s[sa[t] + h[t]] == s[sa[t - 1] + h[t]])
++h[t];
}*/
; i <= L ; ++i)
)
putchar(s[sa[i] - ]);
}
1031 字符加密
1034 泡泡堂
看着很像田忌赛马，贪心策略：①最强的能打过就打，不能跳②；②最弱的能打过就打，不能跳③；③己方最弱送对方最强，看是否平局
有②的原因是有可能当前最强的能够打平，打平之后己方全都满足①，这样就没有必要用最弱的送对方最强了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
;
int zj[MAXN] , cp[MAXN];
int N;
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
N = read();
; i <= N ; ++i)
zj[i] = read();
; i <= N ; ++i)
cp[i] = read();
sort(zj + , zj + N + );
sort(cp + , cp + N + );
, t1 = N , h2 = , t2 = N , sum = ;
; i <= N ; ++i)
if(zj[t1] > cp[t2]){
--t1;
--t2;
sum += ;
}
else
if(zj[t1] < cp[t2]){
++h1;
--t2;
}
else
if(zj[h1] > cp[h2]){
++h1;
++h2;
sum += ;
}
else{
if(zj[h1] == cp[t2])
++sum;
++h1;
--t2;
}
cout << sum << ' ';
swap(cp , zj);
h1 = , t1 = N , h2 = , t2 = N , sum = ;
; i <= N ; ++i)
if(zj[t1] > cp[t2]){
--t1;
--t2;
sum += ;
}
else
if(zj[t1] < cp[t2]){
++h1;
--t2;
}
else
if(zj[h1] > cp[h2]){
++h1;
++h2;
sum += ;
}
else{
if(zj[h1] == cp[t2])
++sum;
++h1;
--t2;
}
cout << N * - sum;
;
}
1034 泡泡堂
1036 树的统计
树剖裸题
#include<bits/stdc++.h>
#define MAXN 30001
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct node{
int l , r , sum , maxN;
}Tree[MAXN << ];
struct Edge{
int end , upEd;
}Ed[MAXN << ];
int head[MAXN] , val[MAXN] , size[MAXN] , dep[MAXN] , son[MAXN] , fa[MAXN];
int N , Q , cntEd , ts , top[MAXN] , ind[MAXN] , rk[MAXN];
inline int max(int a , int b){
return a > b ? a : b;
}
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void dfs1(int dir , int father , int depth){
size[dir] = ;
dep[dir] = depth;
fa[dir] = father;
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(Ed[i].end != father){
dfs1(Ed[i].end , dir , depth + );
size[dir] += size[Ed[i].end];
if(size[Ed[i].end] > size[son[dir]])
son[dir] = Ed[i].end;
}
}
void dfs2(int dir , int t){
top[dir] = t;
ind[dir] = ++ts;
rk[ts] = dir;
if(!son[dir])
return;
dfs2(son[dir] , t);
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(son[dir] != Ed[i].end && fa[dir] != Ed[i].end)
dfs2(Ed[i].end , Ed[i].end);
}
inline void pushup(int dir){
Tree[dir].sum = Tree[dir << ].sum + Tree[dir << | ].sum;
Tree[dir].maxN = max(Tree[dir << ].maxN , Tree[dir << | ].maxN);
}
void init(int dir , int l , int r){
Tree[dir].l = l;
Tree[dir].r = r;
if(l == r)
Tree[dir].sum = Tree[dir].maxN = val[rk[l]];
else{
init(dir << , l , l + r >> );
init(dir << | , (l + r >> ) + , r);
pushup(dir);
}
}
void change(int dir , int poi , int mark){
if(Tree[dir].l == Tree[dir].r){
Tree[dir].maxN = Tree[dir].sum = mark;
return;
}
Tree[dir].l + Tree[dir].r >> >= poi ? change(dir << , poi , mark) : change(dir << | , poi , mark);
pushup(dir);
}
int Query_Max(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r)
return Tree[dir].maxN;
;
)
maxN = max(maxN , Query_Max(dir << , l , r));
)
maxN = max(maxN , Query_Max(dir << | , l , r));
return maxN;
}
int Query_Sum(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r)
return Tree[dir].sum;
;
)
sum = Query_Sum(dir << , l , r);
)
sum += Query_Sum(dir << | , l , r);
return sum;
}
inline void work1(int x , int y){
change( , ind[x] , y);
}
inline int work2(int x , int y){
;
while(fx - fy)
if(dep[fx] >= dep[fy]){
maxN = max(maxN , Query_Max( , ind[fx] , ind[x]));
x = fa[fx];
fx = top[x];
}
else{
maxN = max(maxN , Query_Max( , ind[fy] , ind[y]));
y = fa[fy];
fy = top[y];
}
, ind[x] , ind[y])) : max(maxN , Query_Max( , ind[y] , ind[x]));
}
inline int work3(int x , int y){
;
while(fx - fy)
if(dep[fx] >= dep[fy]){
sum += Query_Sum( , ind[fx] , ind[x]);
x = fa[fx];
fx = top[x];
}
else{
sum += Query_Sum( , ind[fy] , ind[y]);
y = fa[fy];
fy = top[y];
}
, ind[x] , ind[y]) : sum + Query_Sum( , ind[y] , ind[x]);
}
];
int main(){
N = read();
; i < N ; i++){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
; i <= N ; i++)
val[i] = read();
dfs1( , , );
dfs2( , );
init( , , N);
for(int Q = read() ; Q ; Q--){
scanf("%s" , s);
int a = read() , b = read();
] == 'C')
work1(a , b);
else
] == 'M')
printf("%d\n" , work2(a , b));
else
printf("%d\n" , work3(a , b));
}
;
}
1036 树的统计
1037 生日聚会
设$f_{i,j,k,l}$表示放好了$i$个男生、$j$个女生、当前后缀男生-女生最大值为$k$、女生-男生最大值为$l$的方案数
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
][][][];
int main(){
#ifndef ONLINE_JUDGE
freopen("2592.in" , "r" , stdin);
//freopen("2592.out" , "w" , stdout);
#endif
int N = read() , M = read() , K = read();
dp[][][][] = ;
; i <= N ; ++i)
; j <= M ; ++j)
; k <= K ; ++k)
; l <= K ; ++l)
if(dp[i][j][k][l]){
if(i < N && k < K)
(dp[i + ][j][k + ][max(l - , )] += dp[i][j][k][l]) %= MOD;
if(j < M && l < K)
(dp[i][j + ][max(k - , )][l + ] += dp[i][j][k][l]) %= MOD;
}
;
; i <= K ; ++i)
; j <= K ; ++j)
sum = (sum + dp[N][M][i][j]) % MOD;
cout << sum;
;
}
1037 生日聚会
1038 瞭望塔
显然塔顶位置要在所有山坡对应直线的半平面交内，而山坡和半平面交边界都是折线，所以最优点的塔的横坐标一定是山坡折点和半平面交折点之一，通过二分求高度。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<iomanip>
#define eps 1e-12
//This code is written by Itst
using namespace std;
#define ld long double
bool cmp(ld a , ld b){return a - eps < b && a + eps > b;}
struct comp{
ld x , y;
comp(ld _x = , ld _y = ) : x(_x) , y(_y){}
comp operator +(comp a){return comp(x + a.x , y + a.y);}
comp operator -(comp a){return comp(x - a.x , y - a.y);}
comp operator *(ld a){return comp(x * a , y * a);}
ld operator *(comp a){return x * a.x + y * a.y;}
ld operator %(comp a){return x * a.y - y * a.x;}
ld dir()const{return atan2(y , x);}
bool operator <(const comp a)const{return dir() < a.dir();}
bool operator ==(const comp a)const{return cmp(dir() , a.dir());}
}now[] , inter[];
struct line{
comp pos , dir;
;}
}cur[];
];
comp intersect(line a , line b){
ld t = (b.dir % (a.pos - b.pos)) / (a.dir % b.dir);
return a.pos + a.dir * t;
}
bool chk(line a , line b , line c){
;
}
void create(){
hd = tl = ;
que[] = ;
; i < N ; ++i){
].dir) continue;
]] , cur[i]))
--tl;
]] , cur[i]))
++hd;
que[++tl] = i;
}
]] , cur[que[hd]]))
--tl;
; i <= tl ; ++i)
inter[i] = intersect(cur[que[i]] , cur[que[i - ]]);
}
ld calc(line a , ld b){
) , comp( , )}).y;
}
ld search(ld pos){
int L = hd , R = tl;
while(L < R){
;
inter[mid + ].x <= pos ? L = mid + : R = mid;
}
return calc(cur[que[L]] , pos);
}
int binary(ld pos){
, R = N;
while(L < R){
) >> ;
now[mid].x >= pos ? R = mid - : L = mid;
}
return L;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
cin >> N;
; i <= N ; ++i)
cin >> now[i].x;
; i <= N ; ++i)
cin >> now[i].y;
; i < N ; ++i){
cur[i].pos = now[i];
cur[i].dir = now[i + ] - now[i];
}
sort(cur + , cur + N);
create();
vector < long double > vec;
; i <= N ; ++i)
vec.push_back(now[i].x);
; i <= tl ; ++i)
vec.push_back(inter[i].x);
sort(vec.begin() , vec.end());
ld ans = 1e20;
; i < vec.size() ; ++i){
ld t = vec[i];
int pos = binary(t);
ans = min(ans , search(t) - calc((line){now[pos] , now[pos + ] - now[pos]} , t));
}
cout << ) << ans;
;
}
1038 瞭望塔
1040-1049
1040 骑士
基环树DP，先把链上的统计好，然后环上单独DP。
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
;
, dp[MAXN][] , dp2[MAXN][][];
int fa[MAXN] , val[MAXN] , in[MAXN] , N;
bool vis[MAXN] , inCir[MAXN];
queue < int > q;
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read();
; i <= N ; ++i){
val[i] = read();
dp[i][] += val[i];
fa[i] = read();
++in[fa[i]];
}
; i <= N ; ++i)
if(!in[i])
q.push(i);
while(!q.empty()){
int t = q.front();
vis[t] = ;
q.pop();
dp[fa[t]][] += max(dp[t][] , dp[t][]);
dp[fa[t]][] += dp[t][];
if(!--in[fa[t]])
q.push(fa[t]);
}
; i <= N ; ++i)
if(!vis[i]){
int t = i , p = fa[t];
vis[t] = ;
dp2[t][][] = dp[t][];
dp2[t][][] = dp[t][];
while(p != i){
vis[p] = ;
dp2[p][][] = dp[p][] + max(dp2[t][][] , dp2[t][][]);
dp2[p][][] = dp[p][] + max(dp2[t][][] , dp2[t][][]);
dp2[p][][] = dp[p][] + dp2[t][][];
dp2[p][][] = dp[p][] + dp2[t][][];
t = p;
p = fa[t];
}
ans += max(dp2[t][][] , max(dp2[t][][] , dp2[t][][]));
}
cout << ans;
;
}
1040 骑士
1041 圆上的整点
看完这个就会了
什么？你说没看过这个考场上遇到了怎么办？爆零呗
#include<bits/stdc++.h>
#define int long long
//This code is written by Itst
using namespace std;
signed main(){
#ifndef ONLINE_JUDGE
//freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
, N;
cin >> N;
))
N >>= ;
; i * i <= N ; ++i)
){
;
){
++cnt;
N /= i;
}
) == )
times *= (cnt * + );
}
)
) == )
times = times * ;
cout << times * 4ll;
;
}
1041 圆上的整点
1042 硬币购物
做完全背包，然后容斥哪一些硬币拿出的数量超过限制（容斥还是很难想到的）
#include<bits/stdc++.h>
#define int long long
using namespace std;
] = {} , mon[] , e[] , ans;
void dfs(int num , int cnt , int sum){
)
return;
){
ans += (cnt & ? - : ) * times[sum];
return;
}
dfs(num + , cnt , sum);
dfs(num + , cnt + , sum - (e[num] + ) * mon[num]);
}
main(){
ios::sync_with_stdio();
cin.tie();
cout.tie();
int tot;
cin >> mon[] >> mon[] >> mon[] >> mon[] >> tot;
; i < ; i++)
; j <= - mon[i] ; j++)
times[j + mon[i]] += times[j];
while(tot--){
int s;
cin >> e[] >> e[] >> e[] >> e[] >> s;
ans = ;
dfs( , , s);
cout << ans << endl;
}
;
}
1042 硬币购物
1044 木棍分割
第一问二分，第二问前缀和优化DP，注意转移点
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
;
][] , sum[] , num[] , point[] , N , M;
bool check(int mid){
, cnt = ;
; i <= N ; i++)
if(num[i] > mid)
;
else
if(sum + num[i] <= mid)
sum += num[i];
else{
sum = num[i];
cnt++;
}
return cnt <= M;
}
int main(){
N = read();
M = read();
; i <= N ; i++)
num[i] = read();
, R = ;
while(L < R){
;
check(mid) ? R = mid : L = mid + ;
}
printf("%d " , L);
; i <= N ; i++)
sum[i] = sum[i - ] + num[i];
; i <= N ; i++)
dp[][i] = dp[][i - ] + (sum[i] <= L);
, p = ;
; i <= N ; i++){
while(sum[i] - sum[p] > L)
p++;
point[i] = p;
}
num = dp[][N] - dp[][N - ];
; i <= M ; i++){
now ^= ;
memset(dp[now] , , sizeof(dp[now]));
for(int j = i ; j <= N ; j++)
dp[now][j] = (dp[now][j - ] + dp[now ^ ][j - ] - dp[now ^ ][point[j] - ] + MOD) % MOD;
num = (num + dp[now][N] - dp[now][N - ] + MOD) % MOD;
}
cout << num;
;
}
1044 木棍分割
1045 糖果传递
环形均分纸牌
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c)) c = getchar();
) + (a << ) + (c ^ ') , c = getchar();
return a;
}
inline int abs(int a){
? a : -a;
}
];
int main(){
int n = read();
;
; i <= n ; i++)
sum += S[i] = read();
sum /= n;
; i <= n ; i++)
S[i] += S[i - ] - sum;
sort(S + , S + n + );
sum = ;
; i <= n ; i++)
sum += abs(S[i] - S[n + >> ]);
printf("%lld" , sum);
;
}
1045 糖果传递
1046 上升序列
DP出每一个数字之后能够接的最长的上升序列的长度，对于每一个询问贪心地选择尽可能前面的数字。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#define INF 0x3f3f3f3f
#define int long long
#define PII pair < int , int >
#define st first
#define nd second
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
] , maxN[] , num[] , N , cnt;
signed main(){
#ifndef ONLINE_JUDGE
//freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
maxN[] = 1e9;
; i <= N ; ++i)
num[i] = read();
for(int i = N ; i ; --i){
, R = cnt;
while(L < R){
) >> ;
maxN[mid] > num[i] ? L = mid : R = mid - ;
}
dp[i] = L + ;
if(L == cnt)
++cnt;
maxN[L + ] = num[i];
}
for(int M = read() ; M ; --M){
int L = read();
if(cnt < L)
puts("Impossible");
else{
;
; i <= N && L ; ++i)
if(dp[i] >= L && num[bef] < num[i]){
cout << num[i] << ' ';
bef = i;
--L;
}
putchar('\n');
}
}
;
}
1046 上升序列
1047 理想的正方形
二维ST表or二维单调队列
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c)) c = getchar();
) + (a << ) + (c ^ ') , c = getchar();
return a;
}
][][][] , N , lgN , a , b , poww[] = {};
inline int max(int a , int b){return a > b ? a : b;}
inline int min(int a , int b){return a < b ? a : b;}
int main(){
; i < ; i++) poww[i] = poww[i - ] << ;
a = read(); b = read(); N = read();
lgN = log(N) / log();
; i <= a ; i++)
; j <= b ; j++)
ST[i][j][][] = ST[i][j][][] = read();
; k <= lgN ; k++)
; i <= a - poww[k] + ; i++)
; j <= b - poww[k] + ; j++){
ST[i][j][k][] = max(ST[i][j][k - ][] , max(ST[i][j + poww[k - ]][k - ][] , max(ST[i + poww[k - ]][j + poww[k - ]][k - ][] , ST[i + poww[k - ]][j][k - ][])));
ST[i][j][k][] = min(ST[i][j][k - ][] , min(ST[i][j + poww[k - ]][k - ][] , min(ST[i + poww[k - ]][j + poww[k - ]][k - ][] , ST[i + poww[k - ]][j][k - ][])));
}
;
; i <= a - N + ; i++)
; j <= b - N + ; j++)
minT = min(minT , max(max(max(ST[i][j][lgN][] , ST[i][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j][lgN][])
- min(min(min(ST[i][j][lgN][] , ST[i][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j][lgN][]));
cout << minT;
;
}
1047 理想的正方形 二维ST表
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c)) c = getchar();
) + (a << ) + (c ^ ') , c = getchar();
return a;
}
][];
deque < ][];
inline int min(int a , int b){return a < b ? a : b;}
int main(){
;
a = read(); b = read(); n = read();
; i <= a ; i++){
deque < ];
; j <= b ; j++){
num[i][j] = read();
; p <= ; p++){
if(i - q[j][p].front() == n) q[j][p].pop_front();
while(!q[j][p].empty() && (p ^ (num[q[j][p].back()][j] <= num[i][j])))
q[j][p].pop_back();
q[j][p].push_back(i);
if(j - Q[p].front() == n) Q[p].pop_front();
while(!Q[p].empty() && (p ^ (num[q[Q[p].back()][p].front()][Q[p].back()] <= num[q[j][p].front()][j])))
Q[p].pop_back();
Q[p].push_back(j);
}
if(i >= n && j >= n)
minT = min(minT , num[q[Q[].front()][].front()][Q[].front()] - num[q[Q[].front()][].front()][Q[].front()]);
}
}
cout << minT;
;
}
1047 理想的正方形 二维单调队列
1048 分割矩阵
记忆化搜索
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
][][][][] , sum[][] , N , M , K;
][][][][];
inline int calc(int x1 , int y1 , int x2 , int y2){
][y2] - sum[x2][y1 - ] + sum[x1 - ][y1 - ];
}
int dfs(int x1 , int y1 , int x2 , int y2 , int k){
if(vis[x1][y1][x2][y2][k])
return dp[x1][y1][x2][y2][k];
vis[x1][y1][x2][y2][k] = ;
if(!k)
return dp[x1][y1][x2][y2][k] = calc(x1 , y1 , x2 , y2) * calc(x1 , y1 , x2 , y2);
dp[x1][y1][x2][y2][k] = 0x3f3f3f3f;
for(int i = x1 ; i < x2 ; ++i)
; j < k ; ++j)
dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k] , dfs(x1 , y1 , i , y2 , j) + dfs(i + , y1 , x2 , y2 , k - - j));
for(int i = y1 ; i < y2 ; ++i)
; j < k ; ++j)
dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k] , dfs(x1 , y1 , x2 , i , j) + dfs(x1 , i + , x2 , y2 , k - - j));
return dp[x1][y1][x2][y2][k];
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
N = read();
M = read();
K = read();
; i <= N ; ++i)
; j <= M ; ++j)
sum[i][j] = sum[i - ][j] + sum[i][j - ] - sum[i - ][j - ] + read();
long double s = sum[N][M] * 1.0 / K;
cout << ) << sqrt(( , , N , M , K - ) - * sum[N][M] * s + K * s * s) / K);
;
}
1048 分割矩阵
1050-1059
1050 旅行
枚举最小边，从小到大加边，并查集维护连通性
#include<bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
struct Edge{
int start , end , w;
}Ed[];
] , N , M , S , T , ansMax = inf , ansMin = ;
bool cmp(Edge a , Edge b){
return a.w < b.w;
}
inline int gcd(int a , int b){
int t = a % b;
while(t){
a = b;
b = t;
t = a % b;
}
return b;
}
inline void init(){
; i <= N ; i++)
fa[i] = i;
}
int find(int x){
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
int check(int num){
init();
while(num <= M){
int p = find(Ed[num].start) , q = find(Ed[num].end);
fa[p] = q;
if(find(S) == find(T))
break;
num++;
}
return num;
}
int main(){
cin >> N >> M;
; i <= M ; i++)
cin >> Ed[i].start >> Ed[i].end >> Ed[i].w;
cin >> S >> T;
sort(Ed + , Ed + M + , cmp);
; i <= M ; i++){
int t = check(i);
)
break;
int nowMax = Ed[t].w , nowMin = Ed[i].w;
if((double)ansMax / ansMin > (double)nowMax / nowMin){
ansMax = nowMax;
ansMin = nowMin;
}
}
if(ansMax / ansMin == inf)
cout << "IMPOSSIBLE";
else{
int t = gcd(ansMax , ansMin);
cout << ansMax / t;
if(ansMin != t)
cout << "/" << ansMin / t;
}
;
}
1050 旅行
1051 受欢迎的牛
缩点，检查是否为连通DAG且是否有唯一入点，不满足答案为0，满足答案为唯一入点的size
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c)) c = getchar();
) + a + (c ^ ') , c = getchar();
return a;
}
inline int min(int a , int b){
return a < b ? a : b;
}
] , dfn[] , low[] , ts , inSCC[] , sizeSCC[] , headStack , headSCC;
] , inStack[] , outSCC[];
vector < ];
void dfs(int a){
low[a] = dfn[a] = ++ts;
Stack[++headStack] = a;
vis[a] = inStack[a] = ;
; i < Ed[a].size() ; i++){
if(!vis[Ed[a][i]]) dfs(Ed[a][i]);
else if(!inStack[a]) continue;
low[a] = min(low[a] , low[Ed[a][i]]);
}
if(low[a] == dfn[a]){
headSCC++;
do{
inStack[Stack[headStack]] = ;
inSCC[Stack[headStack]] = headSCC;
sizeSCC[headSCC]++;
}while(Stack[headStack--] != a);
}
}
int main(){
for(int M = read() ; M ; M--){
int a = read() , b = read();
Ed[a].push_back(b);
}
; i <= N ; i++) if(!vis[i]) dfs(i);
; i <= N ; i++)
; !outSCC[inSCC[i]] && j < Ed[i].size() ; j++)
outSCC[inSCC[i]] = inSCC[Ed[i][j]] != inSCC[i];
;
; i <= headSCC ; i++)
if(!outSCC[i]){
if(!ans) ans = sizeSCC[i];
else{
cout << ;
;
}
}
cout << ans;
;
}
1051 受欢迎的牛
1053 反素数
由剪枝：答案分解出的质因数一定是$2,3,5,7,11,13,17,19,23,29$这十个质因数中的前若干个，而且次数一定递减，这样可以大大减少搜索时间。
#include<bits/stdc++.h>
using namespace std;
,,,,,,,,,};
long long maxN , N , maxYS;
inline int max(int a , int b){
return a > b ? a : b;
}
void dfs(int k , long long now , int bef , long long q){
){
if(maxYS < q || maxYS == q && maxN > now){
maxYS = q;
maxN = now;
}
return;
}
;
while(now <= N && cou <= bef){
dfs(k + , now , cou , q * (cou + ));
cou++;
now *= dir[k];
}
}
int main(){
cin >> N;
dfs( , , , );
cout << maxN;
;
}
1053 反素数
1054 移动玩具
压缩状态+BFS
#include<bits/stdc++.h>
using namespace std;
] = { , } , bef[];
int main(){
string s;
, tar = ;
; i >= ; i--){
cin >> s;
; j >= ; j--)
now += (s[ - j] - << (i << ) + j);
}
; i >= ; i--){
cin >> s;
; j >= ; j--)
tar += (s[ - j] - << (i << ) + j);
}
if(now == tar){
cout << ;
;
}
queue < pair < int , int > > q;
q.push(make_pair(now , ));
bef[now] = -;
while(!q.empty()){
pair < int , int > t = q.front();
q.pop();
t.second++;
; i < ; i++)
; j < ; j++)
&& !(j == && i % == ) && (( << i + dir[j])) ^ ( << i))))){
<< i) + ( << i + dir[j]);
if(!bef[m]){
bef[m] = t.first;
if(m == tar){
cout << t.second;
;
}
q.push(make_pair(m , t.second));
}
}
}
;
}
1054 移动玩具
1055 玩具取名
设$dp_{i,j,k}$表示区间$[i,j]$是否能缩为字母$k$，转移枚举中间点，$O(800^3)$竟然能过
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
] , L;
][][] , cg[][][];
];
inline int toInt(char c){
switch(c){
case 'W':
;
case 'I':
;
case 'N':
;
case 'G':
;
}
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c;
}
void input(){
; i < ; ++i)
num[i] = read();
; i < ; ++i)
; j <= num[i] ; ++j){
char a = getc() , b = getc();
cg[toInt(a)][toInt(b)][i] = ;
}
scanf();
L = strlen(s + );
; i <= L ; ++i)
dp[i][i][toInt(s[i])] = ;
}
void work(){
; i ; --i)
; j <= L ; ++j)
for(int k = i ; k < j ; ++k)
; p < ; ++p)
if(dp[i][k][p])
; q < ; ++q)
][j][q])
; r < ; ++r)
if(cg[p][q][r])
dp[i][j][r] = ;
}
char toChar(int c){
switch(c){
:
return 'W';
:
return 'I';
:
return 'N';
:
return 'G';
}
}
void output(){
;
; i < ; ++i)
][L][i]){
f = ;
putchar(toChar(i));
}
if(!f)
puts("The name is wrong!");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
input();
work();
output();
;
}
1055 玩具取名
1056 排名系统
把名字Hash掉，然后使用Splay维护。插入的时候相同权值的人排名按照插入时间从小到大，即插入/更新时间较后的人排名较高。
一定要注意：不要偷懒，下面“错误的输出”写法会TLE，应该直接把对应区间框出来然后输出
然后哨兵节点可能要开到INT_MAX
;
void output(int x){
if(!x) return;
output(lch);
|| !(Tree[x].val + )) return;
lltoS(name[x]);
) return;
output(rch);
}
void out(int x){
nm = ;
find(rt , x - , );
output(Tree[rt].ch[]);
}
错误的输出
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
//This code is written by Itst
using namespace std;
#define ll long long
;
int N , cnt;
ll val , name[MAXN];
];
map < ll , int > app;
#define rt Tree[0].ch[0]
struct node{
] , sz;
ll val;
}Tree[MAXN];
#define lch Tree[x].ch[0]
#define rch Tree[x].ch[1]
inline ll Stoll(){
ll cur = ;
int l = strlen(s);
; i < l ; ++i)
cur = cur * + s[i] - ;
return cur;
}
inline void lltoS(ll num){
; i < ; ++i){
s[i] = num % ;
num /= ;
}
; i >= ; --i)
);
putchar(' ');
}
inline ] == x;}
inline ;}
inline void rot(int x){
bool f = son(x);
];
Tree[x].fa = z; Tree[z].ch[son(y)] = x;
Tree[x].ch[f ^ ] = y; Tree[y].fa = x;
Tree[y].ch[f] = w; if(w) Tree[w].fa = y;
up(y);
}
void splay(int x , int tar){
while(Tree[x].fa != tar){
if(Tree[Tree[x].fa].fa != tar)
rot(son(x) == son(Tree[x].fa) ? Tree[x].fa : x);
rot(x);
}
up(x);
}
void find(int x , int K , int tar){
if(Tree[lch].sz == K) splay(x , tar);
else if(Tree[lch].sz > K) find(lch , K , tar);
, tar);
}
void ins(int &x , ll val , int fa){
if(!x){
Tree[x = cnt].fa = fa; Tree[x].val = val;
splay(x , ); return;
}
ins(Tree[x].ch[Tree[x].val >= val] , val , x);
}
void del(int x){
splay(x , );
find(rt , Tree[lch].sz + , rt);
Tree[rt = rch].fa = ;
Tree[Tree[rch].ch[] = lch].fa = rch;
}
); return Tree[lch].sz;}
void output(int x){
if(!x) return;
output(lch);
lltoS(name[x]);
output(rch);
}
void out(int x){
find(rt , x - , );
find(rt , min(x + , Tree[rt].sz - ) , rt);
output(Tree[Tree[rt].ch[]].ch[]);
}
inline char getc(){
char c = getchar();
while(c == ' ' || c == '\n' || c == '\r')
c = getchar();
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
cnt = ; ins(rt , 1e18 , );
cnt = ; ins(rt , - , );
for(scanf("%d" , &N) ; N ; --N)
if(getc() == '+'){
scanf("%s %lld" , s , &val);
if(app.count(name[++cnt] = Stoll())) del(app[name[cnt]]);
app[name[cnt]] = cnt;
ins(rt , val , );
}
else{
scanf("%s" , s);
]))
printf("%d\n" , getRk(app[Stoll()]));
else{
, l = strlen(s);
; i < l ; ++i)
num = num * + s[i] - ;
out(num);
putchar('\n');
}
}
;
}
1056 排名系统
1057 棋盘制作
第一问最大正方形简单的DP，第二问悬线法+单调栈
话说在Luogu上$O(n^3)$算法能AC，但BZOJ上会TLE（坑了我两次提交）
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
/*char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) a = (a << 3) + (a << 1) + (c ^ '0') , c = getchar();*/
scanf("%d" , &a);
return a;
}
inline int min(int a , int b){
return a < b ? a : b;
}
inline int max(int a , int b){
return a > b ? a : b;
}
][];
][] , zhan[][] , len[][];
int main(){
, maxN2 = , head = , N = read() , M = read();
; i <= N ; ++i)
; j <= M ; ++j){
vis[i][j] = read();
DP[i][j] = ;
&& j - && !(vis[i - ][j - ] ^ vis[i][j]))
][j] ^ vis[i][j]) && (vis[i][j - ] ^ vis[i][j]))
DP[i][j] += min(DP[i - ][j] , min(DP[i - ][j - ] , DP[i][j - ]));
maxN1 = max(maxN1 , DP[i][j]);
}
printf("%d\n" , maxN1 * maxN1);
; i <= N ; i++)
; j <= ; j++){
; k <= M ; k++)
{
;
))
len[k][j]++;
else
len[k][j] = ;
int a = len[k][j];
] > a){
maxN2 = max(maxN2 , zhan[head][] * (zhan[head][] + wid));
wid += zhan[head--][];
}
zhan[++head][] = a;
zhan[head][] = wid + ;
}
while(head){
maxN2 = max(maxN2 , zhan[head][] * zhan[head][]);
zhan[head - ][] += zhan[head][];
--head;
}
}
printf("%d" , maxN2);
;
}
1057 棋盘制作
1058 报表统计
MIN_GAP使用懒惰堆，MIN_SORT_GAP使用平衡树做邻值查找
这题竟然有负数数据
#include<bits/stdc++.h>
#define MAXN 500001
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
];
inline void print(int x){
;
)
fwrite( , stdout);
else{
while(x){
output[--dirN] = x % + ;
x /= ;
}
fwrite(output + dirN , , strlen(output + dirN) , stdout);
}
fwrite( , , stdout);
}
struct Node{
] , num;
}Tree[MAXN << ];
, N , root = ;
];
priority_queue < int , vector < int > , greater < int > > q , erase;
inline int abs(int a){
? a : -a;
}
inline int min(int a , int b){
return a < b ? a : b;
}
inline bool son(int dir){
] == dir;
}
inline void ZigZag(int dir){
bool f = son(dir);
if(Tree[dir].fa == root)
root = dir;
Tree[Tree[dir].son[!f]].fa = Tree[dir].fa;
Tree[Tree[dir].fa].son[f] = Tree[dir].son[!f];
int x = Tree[Tree[dir].fa].fa;
Tree[x].son[son(Tree[dir].fa)] = dir;
Tree[dir].son[!f] = Tree[dir].fa;
Tree[Tree[dir].fa].fa = dir;
Tree[dir].fa = x;
}
inline void Splay(int dir){
while(root != dir)
if(Tree[dir].fa == root)
ZigZag(dir);
else{
if(son(Tree[dir].fa) == son(dir))
ZigZag(Tree[dir].fa);
else
ZigZag(dir);
ZigZag(dir);
}
}
inline void calcMinAll(){
];
if(t){
])
t = Tree[t].son[];
minAll = min(minAll , Tree[root].num - Tree[t].num);
}
t = Tree[root].son[];
if(t){
])
t = Tree[t].son[];
minAll = min(minAll , Tree[t].num - Tree[root].num);
}
}
void insert(int num , int &dir , int fa){
if(!dir){
dir = ++cntNode;
Tree[dir].num = num;
Tree[dir].fa = fa;
Splay(dir);
calcMinAll();
return;
}
if(Tree[dir].num == num)
minAll = ;
else
insert(num , Tree[dir].son[Tree[dir].num < num] , dir);
}
int main(){
N = read();
int M = read();
num[] = Tree[].num = read();
; i <= N ; i++){
start[i] = num[i] = read();
if(minAll)
if(Tree[root].num == num[i])
minAll = ;
else
insert(num[i] , Tree[root].son[Tree[root].num < num[i]] , root);
q.push(abs(num[i] - num[i - ]));
}
while(M--){
scanf("%s" , s);
] == 'I'){
int a = read() , b = read();
if(a - N){
erase.push(abs(num[a] - start[a + ]));
while(!erase.empty() && erase.top() == q.top()){
erase.pop();
q.pop();
}
q.push(abs(b - start[a + ]));
}
q.push(abs(b - num[a]));
num[a] = b;
if(minAll)
insert(b , Tree[root].son[Tree[root].num < b] , root);
}
else
] == 'G')
print(q.top());
else
print(minAll);
}
;
}
1058 报表统计
1059 矩阵游戏
考虑到要满足题设条件需要存在$N$个黑块覆盖了所有行和列，于是在所有黑块的行和列之间连一条边，跑完美匹配即可
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int end , upEd;
}Ed[];
] , match[] , cntEd;
];
inline void add(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
bool dfs(int dir){
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end]){
vis[Ed[i].end] = ;
if(!match[Ed[i].end] || dfs(match[Ed[i].end])){
match[Ed[i].end] = dir;
;
}
}
;
}
int main(){
int T;
for(cin >> T ; T ; T--){
memset(head , , sizeof(head));
memset(match , , sizeof(match));
cntEd = ;
int N;
cin >> N;
; i <= N ; i++)
; j <= N ; j++){
int a;
cin >> a;
if(a)
add(i , j);
}
;
; f && i <= N ; i++){
memset(vis , , sizeof(vis));
f = dfs(i);
}
cout << (f ? "Yes" : "No") << endl;
}
;
}
1059 矩阵游戏
1060-1069
1060 时态同步
贪心+树形DP，每一次把对应节点的所有儿子改成同一时间即可
#include<bits/stdc++.h>
#define MAXN 500001
using namespace std;
inline int read(){
;
;
char c;
fread(&c , , stdin);
while(!isdigit(c)){
;
fread(&c , , stdin);
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
fread(&c , , stdin);
}
return f ? -a : a;
}
struct Edge{
int end , upEd , t;
}Ed[MAXN << ];
int head[MAXN] , size[MAXN] , minT[MAXN] , cntEd;
bool vis[MAXN];
inline int max(int a , int b){return a > b ? a : b;}
inline void add(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].t = c;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
long long dfs(int dir){
;
vis[dir] = ;
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end]){
sum += dfs(Ed[i].end);
if(minT[Ed[i].end] + Ed[i].t >= minT[dir])
sum += (minT[Ed[i].end] + Ed[i].t - minT[dir]) * size[dir];
else
sum += (-minT[Ed[i].end] - Ed[i].t + minT[dir]);
minT[dir] = max(minT[dir] , minT[Ed[i].end] + Ed[i].t);
size[dir]++;
}
return sum;
}
int main(){
int N = read() , S = read();
; i < N ; i++){
int a = read() , b = read() , c = read();
add(a , b , c);
add(b , a , c);
}
cout << dfs(S);
;
}
1060 时态同步
1061 志愿者招募
1063 道路设计
1064 假面舞会
1066 蜥蜴
这种很多人一起跑要求时间最小的题目很多时候使用网络流解决
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define id(i , j) ((i - 1) * C + j)
//This code is written by Itst
using namespace std;
, MAXM = ;
struct Edge{
int end , upEd , f , c;
}Ed[MAXM];
int head[MAXN] , cur[MAXN] , dep[MAXN];
;
queue < int > q;
inline ){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].f = c;
Ed[cntEd].c = d;
head[a] = cntEd;
}
inline bool bfs(){
while(!q.empty())
q.pop();
q.push(S);
memset(dep , , sizeof(dep));
dep[S] = ;
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(Ed[i].f && !dep[Ed[i].end]){
dep[Ed[i].end] = dep[t] + ;
if(Ed[i].end == T){
memcpy(cur , head , sizeof(head));
;
}
q.push(Ed[i].end);
}
}
;
}
inline int dfs(int x , int mF){
if(x == T)
return mF;
;
for(int &i = cur[x] ; i ; i = Ed[i].upEd)
){
int t = dfs(Ed[i].end , min(mF - sum , Ed[i].f));
if(t){
Ed[i].f -= t;
Ed[i ^ ].f += t;
sum += t;
if(sum == mF)
break;
}
}
return sum;
}
int Dinic(){
;
while(bfs())
ans += dfs(S , INF);
return ans;
}
inline char getc(){
char c = getchar();
while(c == ' ' || c == '\n' || c == '\r')
c = getchar();
return c;
}
void input(){
cin >> R >> C >> D;
T = R * C * + ;
; i <= R ; ++i)
; j <= C ; ++j){
addEd(id(i , j) , id(i , j) + R * C , getc() - );
addEd(id(i , j) + R * C , id(i , j) , );
}
; i <= R ; ++i)
; j <= C ; ++j)
if(getc() == 'L'){
addEd(S , id(i , j) , );
addEd(id(i , j) , S , );
++M;
}
; i <= R ; ++i)
; j <= C ; ++j){
, i) , min(C - j + , j)) <= D){
addEd(T , id(i , j) + R * C , );
addEd(id(i , j) + R * C , T , INF);
}
; p <= R ; ++p)
; q <= C ; ++q)
if(i != p || j != q)
<= D){
addEd(id(i , j) + R * C , id(p , q) , INF);
addEd(id(p , q) , id(i , j) + R * C , );
}
}
}
void work(){
cout << M - Dinic();
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
input();
work();
;
}
1066 蜥蜴
1067 降雨量
ST表+离散化，两个不相邻的年份之间要加上一个空缺表示没有信息的年份，分类讨论有点多
#include<bits/stdc++.h>
#define MAXN 100002
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
;
c = getchar();
}
) + (a << ) + (c ^ ') , c = getchar();
return f ? -a : a;
}
inline int max(int a , int b){
return a > b ? a : b;
}
];
];
inline int Query(int a , int b){
if(a > b)
;
)] , ST[b - ( << ()) + ][()]);
}
inline bool ifNeighbor(int a , int b){
)] && ifNei[b - ( << ()) + ][()];
}
int main(){
int N = read();
; i <= N ; i++){
num[i] = read();
ST[i][] = read();
ifNei[i][] = num[i] - num[i - ] == ;
}
; ( << i) <= N ; i++)
; j + ( << i) - <= N ; j++){
ST[j][i] = max(ST[j][i - ] , ST[j + ( << i - )][i - ]);
ifNei[j][i] = ifNei[j][i - ] && ifNei[j + ( << i - )][i - ];
}
for(int M = read() ; M ; M--){
;
if(a > b){
fwrite( , , stdout);
continue;
}
if(a == b){
fwrite( , , stdout);
continue;
}
, num + N + , a) - num , t2 = lower_bound(num + , num + N + , b) - num;
if(num[t2] != b){
t2--;
f++;
}
if(num[t1] != a)
f -= ;
switch(f){
:
fwrite( , , stdout);
break;
:
] && Query(t1 + , t2) != ST[t1][])
fwrite( , , stdout);
else
fwrite( , , stdout);
break;
:
] && Query(t1 , t2 - ) != ST[t2][])
fwrite( , , stdout);
else
fwrite( , , stdout);
break;
default:
] >= ST[t2][] && Query(t1 + , t2) == ST[t2][] && Query(t1 + , t2 - ) < ST[t2][])
, t2))
fwrite( , , stdout);
else
fwrite( , , stdout);
else
fwrite( , , stdout);
}
fwrite( , sizeof(char) , stdout);
}
;
}
1067 降雨量
1068 压缩
想知道std是不是什么$O(n^4)$或者$O(n^5)$的神仙算法……
设$f_{i,j}$表示压缩了串的前$i$个字符，在解压过程中缓冲串为$s_{j,i}$的最小步数，转移枚举放$R$、放$s_i$、放$M$之后放$s_i$
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
][] , N;
string s;
signed main(){
#ifndef ONLINE_JUDGE
//freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
cin >> s;
N = s.size();
s = " " + s;
dp[][] = ;
; i <= N ; ++i){
; j ; --j){
dp[i][j] = dp[i - ][j] + ;
) && - j + ) == + , (i + j) / - j + ))
dp[i][j] = min(dp[i][j] , dp[(i + j) / ][j] + );
}
dp[i][i] = 1e9;
; j < i ; ++j)
dp[i][i] = min(dp[i][i] , dp[i - ][j]);
dp[i][i] += ;
}
int ans = 1e9;
; i <= N ; ++i)
ans = min(ans , dp[N][i]);
cout << ans;
;
}
1068 压缩
1069 最大土地面积
1070-1079
1072 排列
暴搜……
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
string s;
];
void dfs(int cur , long long t){
if(cur > l)
cnt += t % k == ;
; i < ; ++i)
if(times[i]){
--times[i];
dfs(cur + , t * + i);
++times[i];
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int T;
for(cin >> T ; T ; --T){
cin >> s >> k;
memset(times , , sizeof(times));
cnt = ;
l = s.size();
; i < l ; ++i)
++times[s[i] - '];
dfs( , );
cout << cnt << endl;
}
;
}
1072 排列
1073 K短路
A*，每一次将一个状态放入堆中的时候检查当前这个状态是否能够到达终点进行剪枝，这样竟然就能跑得很快……
还有一种奇怪的剪枝：将估价函数定为当前状态到终点的最短路，用平衡树代替堆，当平衡树中点数$> K$时将最后一个决策删掉
但似乎上面这种方法TLE得不行……
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
struct Edge{
int end , upEd , w;
}Ed[] , fan[];
struct zt{
string s;
int dis , qw;
long long clc;
bool operator <(const zt a)const{
return qw == a.qw ? s > a.s : qw > a.qw;
}
}now;
priority_queue < zt > all;
] , head[] , hFan[];
int N , M , K , A , B , cntEd , cntFan;
queue < int > q;
];
inline void addEd(Edge* Ed , int* head , int& cntEd , int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void SPFA(){
memset(dis , 0x3f , sizeof(dis));
dis[B] = ;
q.push(B);
while(!q.empty()){
int t = q.front();
q.pop();
vis[t] = ;
for(int i = hFan[t] ; i ; i = fan[i].upEd)
if(dis[fan[i].end] > dis[t] + fan[i].w){
dis[fan[i].end] = dis[t] + fan[i].w;
if(!vis[fan[i].end]){
vis[fan[i].end] = ;
q.push(fan[i].end);
}
}
}
}
inline bool chk(zt now){
];
if(t == B)
;
long long clc = now.clc;
while(!q.empty())
q.pop();
q.push(t);
while(!q.empty()){
t = q.front();
q.pop();
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(!(clc & (1ll << Ed[i].end))){
clc |= 1ll << Ed[i].end;
if(Ed[i].end == B)
;
q.push(Ed[i].end);
}
}
;
}
inline void ist(zt now){
if(chk(now))
all.push(now);
}
void Astar(){
ist((zt){ , A) , , dis[A] , 1ll << A});
while(!all.empty()){
now = all.top();
all.pop();
];
if(t == B){
if(!--K){
; i < now.s.size() ; ++i){
if(i)
putchar('-');
cout << (int)now.s[i];
}
exit();
}
continue;
}
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(!(now.clc & (1ll << Ed[i].end)) && dis[Ed[i].end] != 0x3f3f3f3f)
ist(zt{now.s + , Ed[i].end) , now.dis + Ed[i].w , now.dis + Ed[i].w + dis[Ed[i].end] , now.clc | (1ll << Ed[i].end)});
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
N = read();
M = read();
K = read();
A = read();
B = read();
; i <= M ; ++i){
int a = read() , b = read() , c = read();
addEd(Ed , head , cntEd , a , b , c);
addEd(fan , hFan , cntFan , b , a , c);
}
SPFA();
Astar();
puts("No");
;
}
1073 K短路 A*
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
struct Edge{
int end , upEd , w;
}Ed[];
struct zt{
string s;
int dis , qw;
long long clc;
bool operator <(const zt a)const{
return qw == a.qw ? s < a.s : qw < a.qw;
}
}now;
set < zt > all;
] , N , M , K , A , B , cntEd;
];
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
#define PII pair < int , int >
#define st first
#define nd second
priority_queue < PII > q1;
inline bool chk(zt& now){
];
long long clc = now.clc;
while(!q1.empty())
q1.pop();
q1.push(PII( , t));
while(!q1.empty()){
PII x = q1.top();
q1.pop();
if(clc & (1ll << x.nd))
continue;
clc |= 1ll << x.nd;
if(x.nd == B){
now.qw = now.dis + -x.st;
now.clc |= 1ll << t;
;
}
for(int i = head[x.nd] ; i ; i = Ed[i].upEd)
if(!(clc & (1ll << Ed[i].end)))
q1.push(PII(x.st - Ed[i].w , Ed[i].end));
}
;
}
inline void ist(zt now){
if(chk(now)){
all.insert(now);
if(all.size() > K)
all.erase(--all.end());
}
}
void Astar(){
ist((zt){ , A) , , , });
while(!all.empty()){
now = *all.begin();
all.erase(all.begin());
];
if(t == B){
if(!--K){
; i < now.s.size() ; ++i){
if(i)
putchar('-');
cout << (int)now.s[i];
}
exit();
}
continue;
}
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(!(now.clc & (1ll << Ed[i].end)))
ist(zt{now.s + , Ed[i].end) , now.dis + Ed[i].w , , now.clc});
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
N = read();
M = read();
K = read();
A = read();
B = read();
; i <= M ; ++i){
int a = read() , b = read() , c = read();
addEd(a , b , c);
}
Astar();
puts("No");
;
}
1073 K短路 带奇怪剪枝的A*(非正解)
1076 奖励关
发现正着推会有后效性（在某一个物品没有吃过的情况下不知道吃还是不吃会更优），所以反着推：设$f_{i,j}$表示前$i$个回合吃过的物品集合为$j$，第$i+1$到$N$个回合吃的物品的价值和期望值，答案为$f_{0,0}$
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
][ << ];
] , need[];
int main(){
#ifndef ONLINE_JUDGE
freopen("2473.in" , "r" , stdin);
//freopen("2473.out" , "w" , stdout);
#endif
int N = read() , K = read();
; i < K ; ++i){
pri[i] = read();
for(int j = read() ; j ; j = read())
need[i] |= << (j - );
}
for(int i = N ; i ; --i)
; j < K ; ++j)
; k < << K ; ++k)
if((k & need[j]) == need[j])
dp[i][k] += max(pri[j] + dp[i + ][k | ( << j)] , dp[i + ][k]) / K;
else
dp[i][k] += dp[i + ][k] / K;
cout << ) << dp[][];
;
}
1076 奖励关
1078 斜堆
对左偏树理解不够深入……
对于当前状态下最后一个插入的点，一定在不断走左子树的那一条链上，且没有右子树
有可能有很多这样的点，如果其中深度最浅的点的左子树大小不为$1$，那么当前插入的就是这个点，因为如果不是，插入当前点之前这个点只有右子树，不满足斜堆的性质。如果左子树大小为$1$，这两个点在当前状态下是等价的，因为要求字典序最小，那就认为是深度较深那个点是当前插入的点
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct node{
] , sz;
}Tree[];
];
int init(int x){
)
;
]) + init(Tree[x].ch[]) + ;
}
void search(int& x){
] == -){
){
ans[++cnt] = Tree[x].ch[];
Tree[x].ch[] = -;
--Tree[x].sz;
}
else{
ans[++cnt] = x;
x = Tree[x].ch[];
}
return;
}
search(Tree[x].ch[]);
swap(Tree[x].ch[] , Tree[x].ch[]);
--Tree[x].sz;
}
int main(){
N = read();
Tree[].ch[] = Tree[].ch[] = -;
; i <= N ; ++i){
Tree[i].ch[] = Tree[i].ch[] = -;
int k = read();
Tree[k >= ? k - : k].ch[k >= ] = i;
}
init();
; i <= N ; ++i)
search(rt);
; i ; --i)
cout << ans[i] << ' ';
;
}
1078 斜堆
1079 着色方案
因为如果剩余的方块数量一一对应，且上一次填的颜色的数量也是一样的话，那么这两个状态就是一样的，所以使用记搜+Hash跑得飞快
#include<bits/stdc++.h>
#define ld long double
using namespace std;
] , pot[] , N , sum;
map < unsigned long long , int > hash;
;
inline unsigned long long Hash(int past){
memcpy(pot , num , sizeof(num));
sort(pot + , pot + N + );
unsigned ;
; i <= N ; i++)
sum = sum * + pot[i];
+ past;
}
int dfs(int all , int past){
)
;
unsigned long long t = Hash(num[past]);
if(hash.count(t))
return hash[t];
;
; i <= N ; i++)
if(i != past && num[i]){
num[i]--;
(sum += dfs(all - , i)) %= MOD;
num[i]++;
}
return hash[t] = sum;
}
int main(){
cin >> N;
; i <= N ; i++){
cin >> num[i];
sum += num[i];
}
cout << dfs(sum , );
;
}
1079 着色方案
1080-1089
1081 超级格雷码
BZOJ没有SPJ，可以使用正常格雷码的生成方式AC掉，也可以在Luogu等有SPJ的OJ提交
如果有SPJ其实就随便枚举就可以了
#include<bits/stdc++.h>
using namespace std;
] , num[] , B , N;
inline int modify(int ind){
|| add[ind] + num[ind] == B){
add[ind] *= -;
modify(ind + );
}
else
num[ind] += add[ind];
}
inline void output(){
; i >= ; i--)
putchar(num[i] < ? num[i] + + 'A');
putchar('\n');
}
int main(){
;
cin >> N >> B;
; i < N ; i++){
add[i] = ;
ans *= B;
}
while(ans--){
output();
modify();
}
;
}
1081 超级格雷码
1082 栅栏
二分答案，每一次选择需求的木板中最短的那一些进行搜索看是否能够匹配。
剪枝：如果当前浪费的木板长度加上需求长度大于有的总木板长度就退出
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c)) c = getchar();
) + (a << ) + (c ^ ') , c = getchar();
return a;
}
] , Have[] , AddNeed[] , t[] , maxN , N , M , sum , waste = ;
bool dfs(int dir , int now){
) ;
;
for(int i = dir ; i <= M ; i++)
if(t[i] >= Need[now]){
]) waste += t[i];
] ? i : , now - )) ;
]) waste -= t[i];
t[i] += Need[now];
}
;
}
inline bool check(){
;
waste = ;
memcpy(t , Have , sizeof(Have));
, AtMid);
}
int main(){
M = read();
; i <= M ; i++) sum += Have[i] = read();
N = read();
; i <= N ; i++) Need[i] = read();
sort(Have + , Have + M + );
sort(Need + , Need + N + );
; i <= N ; i++)
AddNeed[i] = AddNeed[i - ] + Need[i];
, r = N;
while(r - l){
AtMid = r + l + >> ;
if(check()) l = AtMid;
;
}
cout << r;
;
}
1082 栅栏
1083 繁忙的都市
最小生成树
#include<bits/stdc++.h>
using namespace std;
][] , minDir[];
];
int main(){
ios::sync_with_stdio(false);
, k = ;
cin >> N >> M;
memset(num , 0x3f , sizeof(num));
memset(minDir , 0x3f , sizeof(minDir));
vis[] = ;
minDir[] = ;
; i < M ; i++)
{
int a , b , c;
cin >> a >> b >> c;
num[a][b] = num[b][a] = c;
}
; i <= N - ; i++){
int minN = 0x3f3f3f3f , minD;
; j <= N ; j++)
if(!vis[j] && minN > (minDir[j] = min(minDir[j] , num[k][j])))
minN = minDir[minD = j];
vis[k = minD] = ;
maxN = max(maxN , minN);
}
cout << N - << " " << maxN;
;
}
1083 繁忙的都市
1084 最大子矩阵
一直眼瞎看不到$M \leq 2$以为是不可做题
设$f_{i,j,k}$表示现在放了$i$个矩形，第一列考虑了前$j$个，第二列考虑了前$k$个的最大值，枚举转移是在第一列还是第二列，然后枚举转移点即可。时间复杂度$O(KN^3)$
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
][] , sum[][] , dp[][][];
int main(){
int N = read() , M = read() , K = read();
; i <= N ; i++)
; j < M ; j++)
sum[i][j] = (num[i][j] = read()) + sum[i - ][j];
; i <= (M == ? : N) ; i++){
; j <= N ; j++){
; k <= K ; k++)
dp[i][j][k] = max(dp[i][j - ][k] , max(dp[i][j][k - ] , i ? dp[i - ][j][k] : ));
; k < i ; k++)
; l <= K ; l++)
dp[i][j][l] = max(dp[i][j][l] , dp[k][j][l - ] + sum[i][] - sum[k][]);
; k < j ; k++)
; l <= K ; l++)
dp[i][j][l] = max(dp[i][j][l] , dp[i][k][l - ] + sum[j][] - sum[k][]);
if(i == j)
; k < j ; k++)
; l <= K ; l++)
dp[i][i][l] = max(dp[i][i][l] , dp[k][k][l - ] + sum[i][] - sum[k][] + sum[j][] - sum[k][]);
}
}
;
; j <= N ; j++)
; k <= K ; k++)
all = max(all , dp[M == ? : N][j][k]);
cout << all;
;
}
1084 最大子矩阵
1085 骑士精神
IDA*模板题
#include<bits/stdc++.h>
using namespace std;
][] = {"};
][] = {,,,-,,,,-,-,-,-,,-,-,-,};
struct p{
][];
char* operator [](int x){return m[x];}
int step , est;
inline void askEst(){
est = step;
; i < ; i++)
; j < ; j++)
est += (ex[i][j] != m[i][j] && m[i][j] != '*');
}
}t , f;
int ans;
bool dfs(p x , int lasMove){
;
;
x.step++;
x.est++;
; i < ; i++)
; j < ; j++)
if(x[i][j] == '*'){
; k < ; k++)
&& i + dir[k][] >= && i + dir[k][] < && j + dir[k][] >= && j + dir[k][] < ){
f = x;
f[i][j] = f[i + dir[k][]][j + dir[k][]];
if(f[i][j] - ex[i][j]) f.est++;
]][j + dir[k][]] - ex[i + dir[k][]][j + dir[k][]])
f.est--;
f[i + dir[k][]][j + dir[k][]] = '*';
;
}
;
}
}
int main(){
//freopen("knight.in" , "r" , stdin);
//freopen("knight.out" , "w" , stdout);
register int T;
for(scanf("%d" , &T) ; T ; T--){
; i < ; i++)
; j < ; j++)
cin >> t[i][j];
t.step = ;
t.askEst();
; ans <= && !dfs(t , -) ; ans++);
printf( ? - : ans);
}
fclose(stdin);fclose(stdout);
;
}
1085 骑士精神
1086 王室联邦
像树上莫队一样分块就行了
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct Edge{
int end , upEd;
}Ed[MAXN << ];
int head[MAXN] , s[MAXN] , cap[MAXN] , be[MAXN] , N , B , top , cnt , cntEd;
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void dfs(int x , int p){
s[++top] = x;
int bot = top;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(Ed[i].end != p){
dfs(Ed[i].end , x);
if(top - bot >= B){
cap[++cnt] = x;
while(top != bot)
be[s[top--]] = cnt;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
B = read();
; i < N ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
dfs( , );
if(top < B){
;
; !root && i <= top ; ++i){
for(int j = head[s[i]] ; !root && j ; j = Ed[j].upEd)
if(be[Ed[j].end]){
cap[be[Ed[j].end]] = ;
root = be[Ed[j].end];
}
}
if(!root){
cout << ;
;
}
else
; i <= top ; ++i)
be[s[i]] = root;
}
else{
cap[++cnt] = ;
; i <= top ; ++i)
be[s[i]] = cnt;
}
cout << cnt << endl;
; i <= N ; ++i)
cout << be[i] << ' ';
cout << endl;
; i <= cnt ; ++i)
cout << cap[i] << ' ';
;
}
1086 王室联邦
1087 互不侵犯
状压DP，复杂度最大到$O(n^32^{2n})$竟然跑得飞快，实际上可以直接枚举子集
#include<bits/stdc++.h>
#define MOD 1000000009
using namespace std;
] , N , K , tarN , num[];
][][] = {{{}}};
];
int main(){
cin >> N >> K;
maxN[][][] = ;
; i < << N ; i++)
) || i & (i >> ))){
int k = i;
while(k){
num[i]++;
k -= k & -k;
}
}
; i <= ; i++){
; k < << N ; k++)
if(check[k])
; j < << N ; j++)
) || k & (j << )))
for(int q = num[k] ; q + num[j] <= K ; q++)
maxN[i][q + num[j]][j] += maxN[i - ][q][k];
}
;
; i < << N ; i++)
sum += maxN[N][K][i];
cout << sum;
;
}
1087 互不侵犯
1088 扫雷
DP，设$f_{i,0/1,0/1}$表示填到第$i$格，其中第$i-1$与第$i$个格子是否有放雷的方案数，注意第一格与最后一格的特判。
#include<bits/stdc++.h>
using namespace std;
][][] , bomb[];
int main(){
ios::sync_with_stdio();cin.tie();cout.tie();
int N;
cin >> N;
; i <= N ; i++) cin >> bomb[i];
]){
:
num[][][] = ;
break;
:
num[][][] = num[][][] = ;
break;
default:
num[][][] = ;
}
; i <= N ; i++)
]){
:
num[i][][] += num[i - ][][];
break;
:
num[i][][] += num[i - ][][];
num[i][][] += num[i - ][][];
num[i][][] += num[i - ][][];
break;
:
num[i][][] += num[i - ][][];
num[i][][] += num[i - ][][];
num[i][][] += num[i - ][][];
break;
default:
num[i][][] += num[i - ][][];
}
cout << (bomb[N] == ? num[N][][] : bomb[N] == ? num[N][][] : num[N][][] + num[N][][]);
;
}
1088 扫雷
1089 严格n元树
DP，设$f_i$表示深度为$i$的严格n元树数量，$sum_i$表示深度在$[0,i]$的n元树数量，转移考虑第$0$层接的$n$个儿子则有
$f_i = sum_{i-1}^n$-$sum_{i-1}+1$
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;
struct Bignum{
];
int& operator [](int x){return a[x];}
Bignum(){
memset(a , , sizeof(a));
}
Bignum(int b){
memset(a , , sizeof(a));
while(b){
a[++a[]] = b % ;
b /= ;
}
}
Bignum operator =(int b){
return *this = Bignum(b);
}
void input(){
string s;
cin >> s;
a[] = s.size();
; i <= a[] ; ++i)
a[i] = s[s.size() - i] - ';
}
void output(){
])
putchar(');
] ; i ; --i)
putchar(a[i] + ');
putchar('\n');
}
Bignum operator +(Bignum b){
Bignum c;
c[] = max(a[] , b[]);
; i <= c[] ; ++i)
){
c[i] -= ;
++c[i + ];
}
] + ])
++c[];
return c;
}
Bignum operator +=(Bignum b){
return *this = *this + b;
}
Bignum operator -(Bignum b){
Bignum c;
c[] = max(a[] , b[]);
; i <= c[] ; ++i)
){
c[i] += ;
--c[i + ];
}
] && !c[c[]])
--c[];
return c;
}
Bignum operator -=(Bignum b){
return *this = *this - b;
}
Bignum operator *(Bignum b){
])
return b;
Bignum c;
c[] = a[] + b[] - ;
; i <= a[] ; ++i)
; j <= b[] ; ++j)
c[i + j - ] += a[i] * b[j];
; i <= c[] ; ++i)
){
c[i + ] += c[i] / ;
c[i] %= ;
])
++c[];
}
] && !c[c[]])
--c[];
return c;
}
Bignum operator *=(Bignum b){
return *this = *this * b;
}
Bignum operator ^(int a){
Bignum times() , b(*this);
while(a){
)
times *= b;
b *= b;
a >>= ;
}
return times;
}
bool operator >(Bignum b)const{
] > b[])
;
] < b[])
;
] ; i ; --i)
if(a[i] > b[i])
;
else
if(a[i] < b[i])
;
;
}
bool operator >= (Bignum b){
] > b[])
;
] < b[])
;
] ; i ; --i)
if(a[i] > b[i])
;
else
if(a[i] < b[i])
;
;
}
Bignum operator /(Bignum b){
Bignum c , d = *this , e;
c[] = a[] - b[] + ;
] ; i && d[] ; --i){
e = b * (Bignum() ^ (i - ));
; j <= ; ++j)
if(e > d){
c[i] = j - ;
break;
}
else
d -= e;
}
] && !c[c[]])
--c[];
return c;
}
Bignum operator /=(Bignum b){
return *this = *this / b;
}
Bignum operator %(Bignum b){
return *this - *this / b * b;
}
Bignum operator %=(Bignum b){
return *this = *this % b;
}
}dp[] , sum[];
int N , D;
int main(){
#ifndef ONLINE_JUDGE
//freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
cin >> N >> D;
dp[] = ; sum[] = ;
; i <= D ; ++i){
dp[i] = ;
; j <= N ; ++j)
dp[i] *= sum[i - ];
dp[i] = dp[i] - sum[i - ] + ;
sum[i] = sum[i - ] + dp[i];
}
dp[D].output();
;
}
1089 严格n元树
1090-1099
1090 字符串折叠
区间DP，额外一个转移：暴力判断是否整个串可以被折叠成一个部分。注意数字的位数判断，不要漏了括号
#include<bits/stdc++.h>
using namespace std;
][];
string s;
inline bool pd(string s , int dir){
, dir);
for(int i = dir ; i < s.size() ; i += dir)
if(string(s , i , dir) != s1)
;
;
}
int main(){
memset(ans , 0x3f , sizeof(ans));
cin >> s;
int l = s.size();
; i < l ; i++)
ans[i][i] = ;
; i >= ; i--)
; j < l ; j++){
for(int k = i ; k < j ; k++)
ans[i][j] = min(ans[i][j] , ans[i][k] + ans[k + ][j]);
);
; k <= j - i + ; k++)
) % k == && pd(s1 , (j - i + ) / k))
ans[i][j] = min(ans[i][j] , ()) + + ans[i][i + (j - i + ) / k - ]);
}
cout << ans[][l - ];
;
}
1090 字符串折叠
1095 捉迷藏
动态点分治，可以去我的学习笔记里看看qaq
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct Edge{
int end , upEd;
}Ed[MAXN << ];
] , dis[MAXN][] , dep[MAXN] , size[MAXN] , ST[][MAXN << ] , fir[MAXN] , logg2[MAXN << ];
int nowSize , minSize , minInd , ts , N , cntEd;
bool vis[MAXN];
struct pq{
priority_queue < int > now , del;
inline void maintain(){
while(!del.empty() && del.top() == now.top()){
del.pop();
now.pop();
}
}
inline void push(int x){
now.push(x);
}
inline void pop(int x){
del.push(x);
maintain();
}
inline int top(){
return now.empty() ? -INF : now.top();
}
inline int sec(){
if(now.empty())
return -INF;
int t = now.top();
now.pop();
maintain();
int p = now.empty() ? -INF : now.top();
now.push(t);
return p;
}
}ans , cur[MAXN] , ch[MAXN];
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void init_dfs(int now , int fa){
fir[now] = ++ts;
ST[][ts] = now;
dep[now] = dep[fa] + ;
for(int i = head[now] ; i ; i = Ed[i].upEd)
if(Ed[i].end != fa){
init_dfs(Ed[i].end , now);
ST[][++ts] = now;
}
}
inline int cmp(int a , int b){
return dep[a] < dep[b] ? a : b;
}
void init_st(){
logg2[] = -;
; i <= N << ; ++i)
logg2[i] = logg2[i >> ] + ;
; << i <= N << ; ++i)
; j + ( << i) - <= N << ; ++j)
ST[i][j] = cmp(ST[i - ][j] , ST[i - ][j + ( << (i - ))]);
}
inline int LCA(int x , int y){
x = fir[x];
y = fir[y];
if(x < y)
swap(x , y);
];
<< t) + ]);
}
void getSize(int x){
vis[x] = ;
++nowSize;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end])
getSize(Ed[i].end);
vis[x] = ;
}
void getRoot(int x){
vis[x] = size[x] = ;
;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end]){
getRoot(Ed[i].end);
maxN = max(maxN , size[Ed[i].end]);
size[x] += size[Ed[i].end];
}
maxN = max(maxN , nowSize - size[x]);
if(maxN < minSize){
minSize = maxN;
minInd = x;
}
vis[x] = ;
}
inline int getLen(int x , int y){
);
}
int init_dfz(int x , int pre){
nowSize = ;
minSize = INF;
getSize(x);
getRoot(x);
x = minInd;
vis[x] = ;
fa[x][] = pre;
, p = x ; fa[x][i] ; p = fa[x][i++]){
dis[x][i] = getLen(x , fa[x][i]);
fa[x][i + ] = fa[fa[x][i]][];
ch[p].push(dis[x][i]);
}
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end])
cur[x].push(ch[init_dfz(Ed[i].end , x)].top());
cur[x].push();
cur[x].push();
ans.push(cur[x].top() + cur[x].sec());
vis[x] = ;
return x;
}
inline void init(){
init_dfs( , );
init_st();
init_dfz( , );
}
inline void modify(int x){
vis[x] ^= ;
if(vis[x]){
ans.pop(cur[x].top() + cur[x].sec());
cur[x].pop();
cur[x].pop();
ans.push(cur[x].top() + cur[x].sec());
int p = x;
; fa[x][i] ; p = fa[x][i++]){
ans.pop(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
cur[fa[x][i]].pop(ch[p].top());
ch[p].pop(dis[x][i]);
cur[fa[x][i]].push(ch[p].top());
ans.push(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
}
}
else{
ans.pop(cur[x].top() + cur[x].sec());
cur[x].push();
cur[x].push();
ans.push(cur[x].top() + cur[x].sec());
int p = x;
; fa[x][i] ; p = fa[x][i++]){
ans.pop(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
cur[fa[x][i]].pop(ch[p].top());
ch[p].push(dis[x][i]);
cur[fa[x][i]].push(ch[p].top());
ans.push(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
}
}
}
inline int query(){
? - : ans.top();
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1095.in" , "r" , stdin);
//freopen("1095.out" , "w" , stdout);
#endif
N = read();
; i < N ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
init();
for(int M = read() ; M ; --M)
if(getc() == 'G')
printf("%d\n" , query());
else
modify(read());
;
}
1095 捉迷藏
1096 仓库建设
设$dp_i$表示满足前$i$个仓库的最小代价，转移$dp_i = \min\limits_{j=1}^{i-1} \{cnt_j \times dep_i + dp_j \ sum_j\} + C_i + sum_i - cnt_i \times dep_i$，其中$dep_i$表示$i$到山脚的距离，$cnt_i$表示前$i$个仓库的产品量总和，$sum_i$表示将前$i$个仓库的产品全运到山脚的代价
显然是个斜率优化。$cnt_i$单调递增，$dep_i$单调递减，可以使用单调队列优化。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#define int long long
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
#define eps 1e-8
#define ld long double
;
struct line{
int K , B;
line(int k , int b):K(k) , B(b){}
};
deque < line > q;
int sum[MAXN] , cnt[MAXN] , dep[MAXN] , dp[MAXN] , cost[MAXN];
int N;
inline int calc(line a , int b){
return a.K * b + a.B;
}
inline ld calcP(line a , line b){
return 1.0 * (b.B - a.B) / (a.K - b.K);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
; i <= N ; ++i){
dep[i] = read();
cnt[i] = read();
cost[i] = read();
}
; i <= N ; ++i){
dep[i] = dep[N] - dep[i];
sum[i] = sum[i - ] + dep[i] * cnt[i];
cnt[i] += cnt[i - ];
}
q.push_back(line( , ));
; i <= N ; ++i){
&& calc(q[] , dep[i]) > calc(q[] , dep[i]))
q.pop_front();
dp[i] = calc(q.front() , dep[i]) + cost[i] + sum[i] - cnt[i] * dep[i];
line t(cnt[i] , dp[i] - sum[i]);
if(q.back().K == cnt[i])
if(q.back().B < dp[i] - sum[i])
continue;
else
q.pop_back();
&& calcP(t , q[q.size() - ]) > calcP(q[q.size() - ] , q[q.size() - ]))
q.pop_back();
q.push_back(t);
}
cout << dp[N];
;
}
1096 仓库建设
1098 办公楼
就是要找补图中的连通块数量，拿几个队列随便搞搞就行了
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
char c = getchar();
;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = ;
c = getchar();
}
if(c == EOF)
exit();
while(isdigit(c)){
a = a * + c - ;
c = getchar();
}
return f ? -a : a;
}
, MAXM = 2e6 + ;
struct Edge{
int end , upEd;
}Ed[MAXM << ];
int sz[MAXN] , head[MAXN];
int N , M , cntEd , cnt;
queue < int > q;
deque < int > notin , notto , tmp;
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read();
M = read();
; i <= M ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
; i <= N ; ++i)
notin.push_back(i);
while(!notin.empty()){
int t = notin.front();
notin.pop_front();
++cnt;
q.push(t);
while(!q.empty()){
int t = q.front();
q.pop();
++sz[cnt];
notto.clear();
for(int i = head[t] ; i ; i = Ed[i].upEd)
notto.push_back(Ed[i].end);
sort(notto.begin() , notto.end());
tmp.clear();
while(!notin.empty())
if(!notto.empty() && notto.front() == notin.front()){
tmp.push_back(notto.front());
notto.pop_front();
notin.pop_front();
}
else
if(notto.empty() || notin.front() < notto.front()){
q.push(notin.front());
notin.pop_front();
}
else
notto.pop_front();
notin = tmp;
}
}
cout << cnt << '\n';
sort(sz + , sz + cnt + );
; i <= cnt ; ++i)
cout << sz[i] << ' ';
;
}
1098 办公楼