\(accoder\) 用数据告诉我们，找女朋友是个假命题
找（a）
简单推一下柿子，维护总和和平方和
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 200005;
const int mod = 998244353;
int x[maxn], y[maxn];
int n;
int main(){
n = read();
for(int i = 1; i <= n; ++i)x[i] = read(), y[i] = read();
int sx = 0, sy = 0, sxx = 0, syy = 0;
for(int i = 1; i <= n; ++i)sx = (sx + x[i]) % mod;
for(int i = 1; i <= n; ++i)sy = (sy + y[i]) % mod;
for(int i = 1; i <= n; ++i)sxx = (sxx + 1ll * x[i] * x[i] % mod) % mod;
for(int i = 1; i <= n; ++i)syy = (syy + 1ll * y[i] * y[i] % mod) % mod;
for(int i = 1; i <= n; ++i){
int ax = (1ll * x[i] * x[i] % mod * n % mod + sxx - 2ll * x[i] * sx % mod + mod) % mod;
int ay = (1ll * y[i] * y[i] % mod * n % mod + syy - 2ll * y[i] * sy % mod + mod) % mod;
printf("%d\n",(ax + ay) % mod);
}
return 0;
}
女（b）
赛时暴跳父亲切了。。。。。。
比较无语
最后 \(20min\) 想出来了 \(nlog^3n\) 的做法，但是调不出来。。。。
给 \(chino\) 大佬简单讲了一下思路。他切了，\(chino\) 太巨了
顺便帮我调出来了，，，
简单来说，在每个点维护其到其子树内黑点的最短距离 \(dist\)
那么每次查询在他的祖先链上查询 \(min(dist + dep_x - dep_f)\) 即可
考虑如何维护，
链上信息- >树剖
区间修改查询- > 线段树
但是直接取 \(min\) 无法快速消除一个点的影响，于是考虑维护所有点
具体的，在线段树每个节点维护一个 \(multiset\) 表示在当前
code
朋（c）
不会，弃了，数据水，判断必要条件能过
题解: 给每条边一个随机边权，然后FMT求行列式即可
假做法
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 50005;
const int inf = 0x3f3f3f3f;
int n, m;
struct EDG{int u, v, w;}l[maxn];
struct wwl{
int head[maxn], tot = 1;
struct edge{int to, net, val;}e[maxn << 1 | 1];
void add(int u, int v, int w){
e[++tot].net = head[u];
head[u] = tot;
e[tot].to = v;
e[tot].val = w;
}
void link(int u, int v, int w){
add(u, v, w); add(v, u, 0);
}
int dep[maxn], now[maxn];
int s, t;
bool bfs(){
for(int i = 1; i <= n + n + 5; ++i)dep[i] = 0;
queue<int>q; now[s] = head[s]; dep[s] = 1;
q.push(s);
while(!q.empty()){
int x = q.front(); q.pop();
if(x == t)return true;
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(e[i].val > 0 && !dep[v]){
dep[v] = dep[x] + 1;
now[v] = head[v];
q.push(v);
}
}
}
return false;
}
int dfs(int x, int from){
if(x == t || from <= 0)return from;
int res = from, i;
for(i = now[x]; i; i = e[i].net){
int v = e[i].to;
if(dep[v] == dep[x] + 1 && e[i].val > 0){
int k = dfs(v, min(res, e[i].val));
if(k <= 0)dep[v] = 0;
res -= k;
e[i].val -= k;
e[i xor 1].val += k;
if(res <= 0)break;
}
}
now[x] = i;
return from - res;
}
int dinic(){
int mx = 0;
while(bfs())mx += dfs(s, inf);
return mx;
}
bool init(int k){
tot = 1; for(int i = 1; i <= n + n + 5; ++i)head[i] = 0;
s = n + n + 1, t = n + n + 2;
for(int i = 1; i <= m; ++i)if((l[i].w & k) == k)link(l[i].u, l[i].v + n, 1);
for(int i = 1; i <= n; ++i)link(s, i, 1);
for(int i = 1; i <= n; ++i)link(i + n, t, 1);
if(dinic() == n)return true;
else return false;
}
}w;
int ans[129];
int num[129];
bool vis[129];
int main(){
n = read(), m = read();
for(int i = 1; i <= m; ++i)l[i].u = read(), l[i].v = read(), l[i].w = read();
for(int i = 1; i <= m; ++i)++num[l[i].w], vis[l[i].w] = 1;
for(int i = 126; i >= 0; --i){
for(int j = 1; j < 128; j += j)
if((i | j) > i)num[i] += num[i | j];
}
for(int k = 127; k >= 0; --k){
if(num[k] < n)continue;
int f = 127;
for(int j = 1; j < 128; j += j)if((k | j) > k && num[k | j])f &= (k | j);
if(f > k && !vis[k])continue;
ans[k] = w.init(k);
}
for(int i = 0; i <= 127; ++i)printf("%d",ans[i]);
return 0;
}
友（d）
code