1001 Hide-And-Seek Game
题意：给出一颗树，两人在树上特定两点来回走，问最早在那个节点相遇
思路：枚举所有点，看它是否同时在两条链上，如果在，那么结合周期、两人最早到达时间，返回到达时间得到4个同余方程（拓展欧几里得），然后得到最小可能解
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<iostream>
#include<algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false);
#define ll long long
const int N = 6e3 + 10;
const ll INF = 1e18 + 10;
struct edge{
int v;
edge* nex;
}ed[N << 1];
int ptop = 0;
edge* head[N];
inline void add(int u,int v){
ed[ptop].v = v;
ed[ptop].nex = head[u];
head[u] = &ed[ptop++];
}
int fa[N][15],dep[N],lg[N];
inline void dfs(int son,int dad){
fa[son][0] = dad;
dep[son] = dep[dad] + 1;
for(int i = 1;i <= 14;i++) fa[son][i] = fa[fa[son][i - 1]][i - 1];
for(edge* p = head[son];p != NULL;p = p -> nex){
int v = p -> v;
if(v == dad) continue;
dfs(v,son);
}
}
inline int lca(int x,int y){
if(dep[x] < dep[y]) swap(x,y);
while(dep[x] != dep[y]) x = fa[x][lg[dep[x] - dep[y]]];
if(x == y) return x;
for(int i = 14;i >= 0;i--) if(fa[x][i] != fa[y][i]) x = fa[x][i] , y = fa[y][i];
return fa[x][0];
}
inline void flg(int n) {
for(int i = 1;i <= n;i++) lg[i] = lg[i - 1] + (i == (2 << lg[i - 1]));
}
inline ll dis(int x,int y){
return dep[x] + dep[y] - 2*dep[lca(x,y)];
}
ll gc;
inline void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b == 0)
{
gc = a;
x = 1;
y = 0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
return;
}
inline ll _max(ll x,ll y){
return x < y ? y : x;
}
inline ll ask(ll ta,ll tb,ll Ta,ll Tb){
ll x,y;
exgcd(Ta,-Tb,x,y);
if((tb - ta) % gc != 0) return INF;
x *= (tb - ta) / gc,y *= (tb - ta) / gc;
ll no = ta + Ta * x;
ll lcm = abs(Ta*Tb / gc);
ll mi = _max(ta,tb);//no至少要到这个数量，然后no只能变klcm
no -= mi;
if(no < 0){
return ((no % lcm + lcm) % lcm) + mi;
}
else{
return no % lcm + mi;
}
}
inline bool in(int s,int t,int x){
int sx = lca(s,x),tx = lca(t,x),st = lca(s,t);
if(st == sx && tx == x) return 1;
if(st == tx && sx == x) return 1;
return 0;
}
inline void chmin(ll &a,const ll b){
a = a < b ? a : b;
}
int main(){
IOS
flg(N - 1);
int t;cin >> t;
while(t--){
int n,m;cin >> n >> m;
ptop = 0;
for(int i = 1;i <= n;i++) head[i] = NULL;
for(int i = 1;i < n;i++){
int u,v;cin >> u >> v;
add(u,v);
add(v,u);
}
dfs(1,1);
for(int i = 1;i <= m;i++){
ll ans = INF,pre = INF,x = -1;
int As,At,Bs,Bt;cin >> As >> At >> Bs >> Bt;
if(As == Bs){
cout << As << endl;
continue;
}else if(As == At){
if(in(Bs,Bt,As))
cout << As << endl;
else
cout << -1 << endl;
continue;
}else if(Bs == Bt){
if(in(As,At,Bs))
cout << Bs << endl;
else
cout << -1 << endl;
continue;
}
ll Ta = dis(As,At) * 2,Tb = dis(Bs,Bt) * 2;
for(int i = 1;i <= n;i++){
if(in(As,At,i) && in(Bs,Bt,i)){
ll ta = dis(i,As),tb = dis(i,Bs);
chmin(ans,ask(ta,tb,Ta,Tb));
chmin(ans,ask(Ta - ta,tb,Ta,Tb));
chmin(ans,ask(ta,Tb - tb,Ta,Tb));
chmin(ans,ask(Ta - ta,Tb - tb,Ta,Tb));
if(ans != pre)
x = i;
pre = ans;
}
}
cout << x << endl;
}
}
}
1002 City Upgrading
题意：最小支配集
思路：板子
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const ll INF = 1e18 + 10;
ll dp[3][N];//0自己，1儿子，2父亲
int a[N];
vector<int> ed[N];
void dfs(int son,int dad){
dp[0][son] += a[son];
bool fson = 0,f0 = 0;
ll mi = INF;
for(auto v:ed[son]){
if(v == dad) continue;
fson = 1;
dfs(v,son);
dp[0][son] += min(dp[0][v],min(dp[1][v],dp[2][v]));
dp[2][son] += min(dp[0][v],dp[1][v]);
if(dp[0][v] < dp[1][v])
f0 = 1;
else
mi = min(mi,dp[0][v] - dp[1][v]);
dp[1][son] += min(dp[0][v],dp[1][v]);
}
if(!fson)
dp[1][son] = INF;
if(!f0)
dp[1][son] += mi;
}
int main(){
int t;cin >> t;
while(t--){
int n;cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];
dp[0][i] = dp[1][i] = dp[2][i] = 0;
ed[i].clear();
}
for(int i = 1;i < n;i++){
int u,v;cin >> u >> v;
ed[u].push_back(v);
ed[v].push_back(u);
}
dfs(1,1);
cout << min(dp[0][1],dp[1][1]) << endl;
}
}
1005 Cyclically Isomorphic
题意：给出n个字符串，每个长度均为m，q次询问，每次问\(s_{x_i}\ s_{y_i}\)能否通过左右循环移动得到
思路：两倍长度，hash得到最小的hash值记录，询问就看最小hash值是否一样即可(NB)
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);
#define ll long long
const int p = 1e9 + 7;
map<int,int> mp;
int main(){
IOS
int t;cin >> t;
while(t--){
int n,m;cin >> n >> m;
ll tem = 1;
for(int i = 1;i <= m;i++)
tem = (tem * 26) % p;
mp.clear();
string s;
for(int i = 1;i <= n;i++){
cin >> s;
s = s + s;
ll hash = 0,mi;
for(int i = 0;i < m;i++)
hash = (hash*26 + s[i] - 'a' + p) % p;
mi = hash;
for(int i = m;i < 2*m;i++){
hash = (hash*26 + s[i] - 'a' - ((tem * (s[i - m] - 'a')) % p) + p) % p;
mi = min(mi,hash);
}
mp[i] = mi;
}
int q;cin >> q;
while(q--){
int x,y;cin >> x >> y;
if(mp[x] == mp[y])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}
1009 Assertion
我还没看就秒了，绝
题意：m个物品放到n个位置，最多的位置数量至少为d，是否一定成立
思路：懂得都懂
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int main(){
IOS
int t;cin >> t;
while(t--){
ll n,m,d;cin >> n >> m >> d;
if((d - 1) * n < m)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
1012 Play on Tree
题意：树上删边问题博弈问题，\(sg[i]=(sg[k_1]+1)xor(sg[k_2]+1)...(sg[k_m]+1),(dad[k_j]=i)\)
思路：换根得到每个点的sg值即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N = 2e5 + 10,p = 1e9 + 7;
int sg[N];
vector<int> ed[N];
ll qpow(ll x,ll y){
ll ans = 1;
while(y){
if(y&1) ans = (ans * x) % p;
x = (x*x) % p;
y >>= 1;
}
return ans;
}
void dfs1(int son,int dad){
for(auto v:ed[son]){
if(v == dad) continue;
dfs1(v,son);
sg[son] ^= (sg[v] + 1);
}
}
ll ans;
void dfs2(int son,int dad){
if(son == 1){
if(sg[1])
ans++;
}else{
if(sg[son] ^= (sg[dad] + 1))
ans++;
}
int res = sg[son];
for(auto v:ed[son]){
if(v == dad) continue;
sg[son] ^= (sg[v] + 1);
dfs2(v,son);
sg[son] = res;
}
}
int main(){
IOS
int t;cin >> t;
while(t--){
int n;cin >> n;
for(int i = 1;i <= n;i++) ed[i].clear(),sg[i] = 0;
for(int i = 1;i < n;i++){
int u,v;cin >> u >> v;
ed[u].push_back(v);
ed[v].push_back(u);
}
dfs1(1,1);
ans = 0;
dfs2(1,1);
cout << (ans * qpow(n,p - 2)) % p << endl;
}
}