A
发现限制形如选了一条边之后，不能选和它端点相同的边。
我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 (1) 就一定有环，所以这种情况下更有环。
我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 (2) 种染色方式，总方案数就是 (2^{C})，(C) 是连通块大小。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2e5 + 5;
const int ha = 998244353;
int n;
int f[MAXN];
std::vector<P> G[MAXN],rG[MAXN];
inline int find(int x){
return x == f[x] ? x : f[x] = find(f[x]);
}
inline void merge(int x,int y){
x = find(x);y = find(y);
if(x == y) return;
f[x] = y;
}
int main(){
scanf("%d",&n);
FOR(i,1,2*n) f[i] = i;
FOR(i,1,2*n){
int u,v;scanf("%d%d",&u,&v);
G[u].pb(MP(v,i));
rG[v].pb(MP(u,i));
}
FOR(v,1,n){
merge(G[v][0].se,G[v][1].se);
for(auto x:G[v]){
for(auto y:rG[x.fi]){
if(y.se != x.se){
merge(x.se,y.se);
}
}
}
}
int t = 1;
FOR(i,1,2*n) if(find(i) == i) t = 2ll*t%ha;
printf("%d
",t);
return 0;
}
B
设 (t_i) 表示交换 (A_i,A_{i+1}) 的时间，如果存在 (a_i=i) 一定无解。
如果有位置满足 (a_i < i)，那么相当于有限制 (t_{a_i} > t_{a_i+1} > ldots > t_{i-1})，(a_i > i) 也是类似的。
可以用差分（或者直接暴力）处理处相邻两个数的限制，现在变成了相邻两个数有限制 < 或者 > ，求排列方案数。
设 (f_{i,j}) 表示考虑前 (i) 个数，最后一个数的排名是 (j) 的方案数，前缀和优化转移即可。
另一种做法是我们考虑容斥，将 > 容斥为 <，那么新的序列形如若干连通块，大小为 (s_1,s_2,ldots,s_m)，那么方案就是 (inom {n}{s_1,s_2,ldots,s_m})。可以写个 dp：设 (f_{i}) 表示前缀 (i) 的答案，转移枚举最后一段连续段是啥，算上容斥系数一起转移就好了。可以用分治 NTT 优化。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5000+5;
const int ha = 1e9 + 7;
bool vis[MAXN];
int ans = 1;
inline int qpow(int a,int n=ha-2){
int res = 1;
while(n){
if(n & 1) res = 1ll*res*a%ha;
a = 1ll*a*a%ha;
n >>= 1;
}
return res;
}
int fac[MAXN],inv[MAXN];
inline void prework(){
fac[0] = 1;FOR(i,1,MAXN) fac[i] = 1ll*fac[i-1]*i%ha;
inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}
inline int C(int n,int m){
if(n < 0 || m < 0 || n < m) return 0;
return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}
int n,a[MAXN];
char str[MAXN];// i和i+1的关系
int f[MAXN][MAXN],pre[MAXN],suf[MAXN];
inline void add(int &x,int y){
x += y;if(x >= ha) x -= ha;
}
int main(){
prework();scanf("%d",&n);
FOR(i,1,n) scanf("%d",a+i),++a[i];
FOR(i,1,n){
if(a[i] == i){
puts("0");exit(0);
}
if(a[i] < i){
FOR(j,a[i],i-2){
if(str[j] == '<'){
puts("0");
exit(0);
}
str[j] = '>';
}
}
else{
FOR(j,i,a[i]-2){
if(str[j] == '>'){
puts("0");exit(0);
}
str[j] = '<';
}
}
}
f[1][1] = 1;
FOR(i,2,n-1){
pre[0] = suf[i] = 0;
FOR(j,1,i-1) pre[j] = pre[j-1],add(pre[j],f[i-1][j]);
ROF(j,i-1,1) suf[j] = suf[j+1],add(suf[j],f[i-1][j]);
FOR(j,1,i){
if(str[i-1] == '<'){
f[i][j] = pre[j-1];
}
else if(str[i-1] == '>'){
f[i][j] = suf[j];
}
else{
f[i][j] = pre[i-1];
}
}
}
int ans = 0;
FOR(i,1,n-1) add(ans,f[n-1][i]);
printf("%d
",ans);
return 0;
}
C
我们考虑一下不变量：发现任意 (3 imes 3) 的矩阵中，(a_{1,1}+a_{2,3}+a_{3,2}-a_{1,2}-a_{2,1}-a_{3,3}) 是不变的。
这样的矩阵形如：
+ - 0
- 0 +
0 + -
发现无论做什么操作，这个值都不变。
所以我们只要能把前两行前两列都消成 (0) ，如果满足条件，剩下的格子都能推出来是 (0)。
先考虑如何消两行：从左往右考虑每一列，每次先用列操作消去下面的数，再用对角线操作消去上面的数。
消两列同理。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1000+5;
int n,m;LL a[MAXN][MAXN];
struct Node{
int opt,x;LL k;
Node(int opt=0,int x=0,LL k=0) : opt(opt),x(x),k(k) {}
};
std::vector<Node> S;
inline void gao(int opt,int x,LL k){
S.pb(Node(opt,x,k));
if(opt == 1){
FOR(i,1,m) a[x][i] += k;
}
else if(opt == 2){
FOR(i,1,n) a[i][x] += k;
}
else{
// j-i = x
FOR(i,1,n){
int j = i+x;
if(j >= 1 && j <= m) a[i][j] += k;
}
}
}
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,n) FOR(j,1,m) scanf("%lld",&a[i][j]);
ROF(i,n,1){
gao(1,i,-a[i][1]);
gao(3,2-i,-a[i][2]);
}
FOR(i,3,m){
gao(2,i,-a[2][i]);
gao(3,i-1,-a[1][i]);
}
bool flag = 1;
FOR(i,1,n) FOR(j,1,m) flag &= (a[i][j] == 0);
if(!flag) puts("-1");
else{
printf("%d
",(int)S.size());
for(auto x:S) printf("%d %d %lld
",x.opt,x.x,x.k);
}
return 0;
}
D
考试差一点优化。。
首先写出 dp 然后是个经典的斜率优化形式就不用说了。
但是这都不单调，如果直接做是 (O(n^2 log n)) 的。但是我们注意到询问点只有 (O(n)) 个，所以预先对可能的询问点排序，每建完凸包就直接用单调性扫过去回答所有询问即可。(O(n^2+nlog n))
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5000+5;
struct Node{
LL x,y;
Node(LL x=0,LL y=0) : x(x),y(y) {}
inline Node operator + (const Node &t) const {
return Node(x+t.x,y+t.y);
}
inline Node operator - (const Node &t) const {
return Node(x-t.x,y-t.y);
}
inline LL operator * (const Node &t) const {
return x*t.y-y*t.x;
}
inline bool operator < (const Node &t) const {
return x == t.x ? y > t.y : x < t.x;
}
};
int n,a[MAXN];LL sm[MAXN];
LL f[MAXN][MAXN];
std::vector<P> S;
LL w[MAXN][MAXN];
inline LL calc(Node a,LL x){
return -a.x*x+a.y;
}
inline void build(int id){
std::vector<Node> v;
std::deque<Node> tb;
for(auto x:S){
if(x.se < id){
v.pb(Node(sm[x.se],f[id][x.se]-sm[id]*sm[id]+sm[id]*sm[x.se]));
}
}
std::reverse(all(v));
for(auto x:v){
while(tb.size() >= 2 && (tb.back()-tb[(int)tb.size()-2])*(x-tb.back()) >= 0) tb.pop_back();
tb.pb(x);
}
for(auto x:S){
while(tb.size() >= 2 && calc(tb[0],x.fi) <= calc(tb[1],x.fi)) tb.pop_front();
w[id][x.se] = calc(tb[0],x.fi);
}
}
inline void trans(int id){
f[id][0] = 0;
FOR(i,1,id-1){
f[id][i] = w[i][id]+sm[id]*sm[i];
}
}
int main(){
scanf("%d",&n);
FOR(i,1,n) scanf("%d",a+i),sm[i] = sm[i-1]+a[i];
FOR(i,0,n) S.pb(MP(sm[i],i));std::sort(all(S));std::reverse(all(S));
f[1][0] = 0;build(1);
FOR(i,2,n){
trans(i);
build(i);
}
LL ans = 0;
FOR(i,0,n-1) ans = std::max(ans,f[n][i]);
printf("%lld
",ans);
return 0;
}