$$2017-2018 ACM-ICPC, Asia Daejeon Regional Contest$$
(A.Broadcast Stations)
(B.Connect3)
BFS+哈希判重，哈希就用一个16位的三进制数表示即可
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
using LL = int_fast64_t;
struct Matrix{
int mat[4][4],stp[4];
LL hashval;
int curcol;
Matrix(){
memset(mat,0,sizeof(mat));
memset(stp,0,sizeof(stp));
hashval = curcol = 0;
}
};
set<int> vis;
int st,edx,edy;
LL powt[20];
int check(const Matrix& M){
for(int i = 0; i < 4; i++){
for(int j = 0; j < 2; j++){
if(M.mat[i][j]&&M.mat[i][j]==M.mat[i][j+1]&&M.mat[i][j]==M.mat[i][j+2]) return M.mat[i][j];
if(M.mat[j][i]&&M.mat[j][i]==M.mat[j+1][i]&&M.mat[j][i]==M.mat[j+2][i]) return M.mat[j][i];
}
}
int sx[4] = {0,1,0,1};
int sy[4] = {0,0,1,1};
for(int i = 0; i < 4; i++){
int x = sx[i], y = sy[i];
if(M.mat[x][y]&&M.mat[x][y]==M.mat[x+1][y+1]&&M.mat[x][y]==M.mat[x+2][y+2]) return M.mat[x][y];
}
sy[0] = 2, sy[1] = 3, sy[2] = 3, sy[3] = 2;
for(int i = 0; i < 4; i++){
int x = sx[i], y = sy[i];
if(M.mat[x][y]&&M.mat[x][y]==M.mat[x+1][y-1]&&M.mat[x][y]==M.mat[x+2][y-2]) return M.mat[x][y];
}
return 0;
}
int bfs(){
int tot = 0;
queue<Matrix> que;
Matrix start;
start.mat[st][0] = 1;
start.curcol = 1;
start.hashval += powt[4*st];
start.stp[st] = 1;
vis.insert(start.hashval);
que.push(start);
while(!que.empty()){
Matrix now = que.front();
que.pop();
int color = now.curcol ^ 3;
LL hax = now.hashval;
for(int i = 0; i < 4; i++){
int stpos = now.stp[i];
if(stpos==4) continue;
if(i==edx&&stpos==edy){
if(color==1) continue;
LL curhash = hax + powt[4*i+stpos] * color;
if(vis.count(curhash)) continue;
else vis.insert(curhash);
now.mat[i][stpos] = color;
if(check(now)) tot++;
now.mat[i][stpos] = 0;
}
else{
LL curhash = hax + powt[4*i+stpos] * color;
if(vis.count(curhash)) continue;
else vis.insert(curhash);
now.mat[i][stpos] = color;
if(!check(now)){
now.stp[i]++;
now.hashval = curhash;
now.curcol ^= 3;
que.push(now);
now.curcol ^= 3;
now.hashval = hax;
now.stp[i]--;
}
now.mat[i][stpos] = 0;
}
}
}
return tot;
}
int main(){
scanf("%d %d %d",&st,&edx,&edy);
st--,edx--, edy--;
edx^=edy^=edx^=edy;
powt[0] = 1;
for(int i = 1; i <= 18; i++) powt[i] = powt[i-1] * 10;
printf("%d
",bfs());
return 0;
}
(C.Game Map)
先按无向图连边，然后按边连着的两个点的度数重新构图，然后跑记忆化搜索即可
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 3e5+7;
int n,m,deg[MAXN],f[MAXN];
vector<int> G[MAXN],newG[MAXN];
void rebuild(){
for(int u = 1; u <= n; u++){
for(int v : G[u]){
if(deg[v]>deg[u]) newG[u].emplace_back(v);
}
}
}
int solve(int u){
if(f[u]!=-1) return f[u];
f[u] = 0;
for(int v : newG[u]) f[u] = max(f[u],solve(v));
f[u]++;
return f[u];
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= m; i++){
int u,v;
scanf("%d %d",&u,&v);
u++, v++;
G[u].emplace_back(v);
G[v].emplace_back(u);
deg[u]++; deg[v]++;
}
rebuild();
memset(f,255,sizeof(f));
for(int i = 1; i <= n; i++) if(f[i]==-1) solve(i);
printf("%d
",*max_element(f+1,f+1+n));
return 0;
}
(D.Happy Number)
打表找规律
#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main(){
int n; cin>>n;
mp[1]++,mp[19]++,mp[82]++,mp[68]++,mp[100]++;
int t=5;
while(t--){
for(int i=1;i<=999;i++){
int tmp=i, s=0;
while(tmp){
s+=(tmp%10)*(tmp%10);
tmp/=10;
}
if(mp.count(s)){
mp[i]++;
}
}
}
int tmp=n, s=0;
while(tmp){
s+=(tmp%10)*(tmp%10);
tmp/=10;
}
if(mp[s])cout<<"HAPPY";
else cout<<"UNHAPPY";
return 0;
}
(E.How Many to Be Happy?)
对于题给的每一条边，问最少删掉几条边能使这条边出现在最小生成树中
按照Kruskal的方法建最小生成树的时候，是贪心地优先考虑权值小的边，判断这条边连接的两个点是否已经联通。
现在如果要选定一条边加进去，那么必然在遍历到它之前，这条边所连的两个点没有联通，使得这两个点不连通所删掉的最少边就是答案，其实就是最小割的模型，考虑把所有小于该边权值的边加到图中然后跑最大流即可
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 555;
const int INF = 0x3f3f3f3f;
int n,m,rk[MAXN],iter[MAXN];
pair<pair<int,int>,int> es[MAXN];
struct EDGE{
int to,cap,rev;
EDGE(){}
EDGE(int _to, int _cap, int _rev){
to = _to;
cap = _cap;
rev = _rev;
}
};
vector<EDGE> G[MAXN];
void ADDEDGE(int u, int v, int cap){
G[u].emplace_back(EDGE(v,cap,(int)G[v].size()));
G[v].emplace_back(EDGE(u,0,(int)G[u].size()-1));
}
bool BFS(int S, int T){
queue<int> que;
memset(iter,0,sizeof(iter));
memset(rk,0,sizeof(rk));
rk[S] = 1;
que.push(S);
while(!que.empty()){
int u = que.front();
que.pop();
for(auto e : G[u]){
if(!e.cap || rk[e.to]) continue;
rk[e.to] = rk[u] + 1;
que.push(e.to);
}
}
return rk[T]!=0;
}
int dfs(int u, int T, int f){
if(u==T) return f;
for(int &i = iter[u]; i < (int)G[u].size(); i++){
EDGE &e = G[u][i];
if(!e.cap || rk[e.to]!=rk[u]+1) continue;
int d = dfs(e.to,T,min(f,e.cap));
if(d){
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
return 0;
}
int Dinic(int S, int T){
int flow = 0;
while(BFS(S,T)){
int d = dfs(S,T,INF);
while(d){
flow += d;
d = dfs(S,T,INF);
}
}
return flow;
}
int solve(int ID){
for(int i = 0; i < MAXN; i++) G[i].clear();
int S = es[ID].first.first, T = es[ID].first.second;
for(int i = 1; i <= m; i++){
if(es[i].second>=es[ID].second) break;
ADDEDGE(es[i].first.first,es[i].first.second,1);
ADDEDGE(es[i].first.second,es[i].first.first,1);
}
return Dinic(S,T);
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= m; i++) scanf("%d %d %d",&es[i].first.first,&es[i].first.second,&es[i].second);
sort(es+1,es+1+m,[](const pair<pair<int,int>,int> &A, const pair<pair<int,int>,int> &B){
return A.second < B.second;
});
int res = 0;
for(int i = 1; i <= m; i++) res += solve(i);
printf("%d
",res);
return 0;
}
(F.Philosopher's Walk)
按每一步所在块的位置（1/4为1块）递归即可，注意坐标变换
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
int n,m;
pair<int,int> solve(int k, int step){
if(k==1){
if(step==1) return make_pair(1,1);
else if(step==2) return make_pair(1,2);
else if(step==3) return make_pair(2,2);
else return make_pair(2,1);
}
int tot = (1<<k)<<k;
int perstep = tot>>2;
if(step>perstep*3){
auto p = solve(k-1,step-perstep*3);
return make_pair((1<<k)+1-p.second,(1<<(k-1))+1-p.first);
}
else if(step>perstep*2){
auto p = solve(k-1,step-perstep*2);
return make_pair((1<<(k-1))+p.first,(1<<(k-1))+p.second);
}
else if(step>perstep){
auto p = solve(k-1,step-perstep);
return make_pair(p.first,(1<<(k-1))+p.second);
}
else{
auto p = solve(k-1,step);
return make_pair(p.second,p.first);
}
}
int main(){
scanf("%d %d",&n,&m);
auto p = solve(log2(n),m);
printf("%d %d
",p.first,p.second);
return 0;
}
(G.Rectilinear Regions)
给出两条阶梯型折线，问B线在A线上面所围成的面积有多少，一共有多少块围成的区域
如果两折线的单调性不一样的话就直接输出0，如果都是单调递减的话把两条线都关于x轴对称翻着就是两个单调递增的阶梯折线了
扫描一遍就完了
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+7;
using LL = int_fast64_t;
int ya,yb,n,m,tot,x;
pair<pair<int,int>,int> vert[MAXN<<1];
int main(){
scanf("%d %d",&n,&m);
int d1,d2;
scanf("%d",&ya);
for(int i = 1; i <= n; i++){
tot++;
vert[tot].second = 0;
scanf("%d %d",&vert[tot].first.first,&vert[tot].first.second);
d1 = vert[tot].first.second>ya?1:-1;
}
scanf("%d",&yb);
for(int i = 1; i <= m; i++){
tot++;
vert[tot].second = 1;
scanf("%d %d",&vert[tot].first.first,&vert[tot].first.second);
d2 = vert[tot].first.second>yb?1:-1;
}
if(d1!=d2) return puts("0 0"), 0;
if(d1<0){
ya *= -1;
yb *= -1;
swap(ya,yb);
for(int i = 1; i <= tot; i++) {
vert[i].first.second *= -1;
vert[i].second ^= 1;
}
}
sort(vert+1,vert+1+tot,[](const pair<pair<int,int>,int> &A, const pair<pair<int,int>,int> &B){
return A.first.first < B.first.first;
});
int cur = 1;
while(cur <= tot){
int tpya = ya;
int tpyb = yb;
if(vert[cur].second==1){
tpyb = vert[cur].first.second;
if(ya<yb) ya = tpya, yb = tpyb;
else{
if(tpya<tpyb){
x = vert[cur].first.first;
ya = tpya, yb = tpyb;
cur++;
break;
}
else ya = tpya,yb = tpyb;
}
}
else ya = vert[cur].first.second;
cur++;
}
LL area = 0, tparea = 0, regions = 0;
bool tag = true;
for(int i = cur; i <= tot; i++){
if(vert[i].second==0){
if(tag){
tparea += 1ll * (vert[i].first.first-x) * (yb-ya);
ya = vert[i].first.second;
x = vert[i].first.first;
if(ya>=yb){
tag = false;
area += tparea;
regions++;
tparea = 0;
}
}
else{
ya = vert[i].first.second;
x = vert[i].first.first;
}
}
else{
if(tag){
tparea += 1ll * (vert[i].first.first-x) * (yb-ya);
yb = vert[i].first.second;
x = vert[i].first.first;
}
else{
yb = vert[i].first.second;
x = vert[i].first.first;
if(yb>ya) tag = true;
}
}
}
printf("%I64d %I64d
",regions,area);
return 0;
}
(H.Rock Paper Scissors)
先把字符串转化一下，把要匹配的字符变成相同字符，把每个字符分开来考虑，然后把两个字符串看作两个多项式(f(x),g(x))，把当前考虑匹配的字符的系数设为(1)，不是需要匹配的系数设为(0)，则初始匹配点为(pos)答的案就是(ans[pos]=sum_{i=0}^{m-1}f[pos+i]*g[i])
把第二个串翻转得到：(ans[pos]=sum_{i=0}^{m-1}f[pos+i]g[m-1-i])答案就是(f)和(g)卷积的第(pos+m-1)次项的系数
分三次每次做三次FFT即可
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 4e5+7;
const double Pi = acos(-1);
int n,m,limit,l,r[MAXN],ans[MAXN];
char s[MAXN],t[MAXN];
char RSP[3] = {'R','S','P'};
struct Complex{
double x,y;
Complex(double _x = 0, double _y = 0){ x = _x; y = _y; }
Complex operator + (const Complex rhs){ return Complex(x+rhs.x,y+rhs.y); }
Complex operator - (const Complex rhs){ return Complex(x-rhs.x,y-rhs.y); }
Complex operator * (const Complex rhs){ return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x); }
}A[MAXN],B[MAXN];
void FFT(Complex *arr, int inv){
for(int i = 0; i < limit; i++) if(i<r[i]) swap(arr[i],arr[r[i]]);
for(int len = 1; len < limit; len <<= 1){
Complex wn(cos(Pi/len),inv*sin(Pi/len));
for(int R = 0; R < limit; R += (len<<1)){
Complex w(1,0);
for(int i = R; i < R+len; i++,w = w*wn){
Complex x = arr[i];
Complex y = w * arr[i+len];
arr[i] = x + y;
arr[i+len] = x - y;
}
}
}
}
int main(){
scanf("%d %d %s %s",&n,&m,s,t);
for(int i = 0; i < m; i++){
if(t[i]=='R') t[i] = 'S';
else if(t[i]=='S') t[i] = 'P';
else t[i] = 'R';
}
limit = 1, l = 0;
while(limit<=n+m) limit <<= 1, l++;
for(int i = 0; i < limit; i++) r[i] = ((r[i>>1]>>1) | ((i&1)<<(l-1)));
reverse(t,t+m);
for(int ch = 0; ch < 3; ch++){
for(int i = 0; i < limit; i++){
A[i].x = A[i].y = 0;
B[i].x = B[i].y = 0;
}
for(int i = 0; i < n; i++) if(s[i]==RSP[ch]) A[i].x = 1;
for(int i = 0; i < m; i++) if(t[i]==RSP[ch]) B[i].x = 1;
FFT(A,1);
FFT(B,1);
for(int i = 0; i < limit; i++) A[i] = A[i] * B[i];
FFT(A,-1);
for(int i = 0; i < limit; i++) ans[i] += (int)(A[i].x/limit+0.5);
}
int maxx = 0;
for(int i = 0; i < n; i++) maxx = max(maxx,ans[m+i-1]);
printf("%d
",maxx);
return 0;
}
(I.Slot Machines)
找起始位置+最小循环节的最小值，可以把每个位置开始的最小循环节找出来然后枚举一下即可
把串翻转然后建出Next数组，i点开始向前的最小循环节长度就是(i-next[i])
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e6+7;
int n,k,p,A[MAXN],f[MAXN];
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&A[i]);
int len = 0, ptr = 2;
k = n-1, p = 1;
reverse(A+1,A+1+n);
f[1] = 0;
while(ptr<=n){
if(A[ptr]==A[len+1]) f[ptr++] = ++len;
else{
if(len) len = f[len];
else f[ptr++] = len;
}
}
for(int i = 1; i <= n; i++){
int tp = i - f[i];
int tk = n - i;
if(tp+tk<p+k||(tp+tk==p+k&&p>tp)){
p = tp;
k = tk;
}
}
printf("%d %d
",k,p);
return 0;
}
(J.Strongly Matchable)
(K.Untangling Chain)
和初始长度无关，只和方向有关，考虑从当前点开始往某个方向延伸出一条边，到达某个终止位置，只要这个位置的两侧都没有任何其他点，下一次折线必然可以选出一个性质相同的位置，记录两个坐标轴访问最左端的位置和最右端的位置即可。
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2e5+7;
const int O = 1e5;
int n,xmin,xmax,ymin,ymax;
int main(){
scanf("%d",&n);
int curdir = 0, cx = O, cy = O;
xmin = xmax = ymin = ymax = O;
for(int i = 1; i <= n; i++){
if(curdir==0){
printf("%d ",ymax+1-cy);
ymax = cy = ymax+1;
}
else if(curdir==1){
printf("%d ",xmax+1-cx);
xmax = cx = xmax+1;
}
else if(curdir==2){
printf("%d ",cy-ymin+1);
ymin = cy = ymin-1;
}
else if(curdir==3){
printf("%d ",cx-xmin+1);
xmin = cx = xmin-1;
}
int dir;
scanf("%d %d",&dir,&dir);
curdir = (curdir+dir+4)%4;
}
puts("");
return 0;
}
(L.Vacation Plans)
枚举天数找最短路，天数上限大概是(n^3)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 55;
const int MAXNP = MAXN * MAXN * MAXN;
using LL = int_fast64_t;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int p;
struct Country{
int n,m,h[MAXN],airport;
LL f[MAXNP][MAXN];
struct EDGE{
int u, v, c;
EDGE(){}
EDGE(int _u, int _v, int _c){ u = _u, v = _v, c = _c; }
};
vector<EDGE> G;
}cont[4];
int main(){
scanf("%d",&p);
for(int pp = 1; pp <= p; pp++){
scanf("%d %d",&cont[pp].n,&cont[pp].m);
for(int i = 1; i <= cont[pp].n;i++) scanf("%d",&cont[pp].h[i]);
for(int i = 1; i <= cont[pp].m; i++){
int u, v, c;
scanf("%d %d %d",&u,&v,&c);
cont[pp].G.emplace_back(Country::EDGE(u,v,c));
}
scanf("%d",&cont[pp].airport);
}
for(int k = 1; k <= p; k++){
memset(cont[k].f,INF,sizeof(cont[k].f));
cont[k].f[0][1] = 0;
for(int day = 1; day < MAXNP; day++){
for(int i = 1; i <= cont[k].n; i++) cont[k].f[day][i] = min(cont[k].f[day][i],cont[k].f[day-1][i]+cont[k].h[i]);
for(auto e : cont[k].G) cont[k].f[day][e.v] = min(cont[k].f[day][e.v],cont[k].f[day-1][e.u]+e.c);
}
}
LL res = INF;
for(int i = 0; i < MAXNP; i++){
LL tot = 0;
for(int k = 1; k <= p; k++){
if(cont[k].f[i][cont[k].airport]==INF){
tot = INF;
break;
}
tot += cont[k].f[i][cont[k].airport];
}
res = min(res,tot);
}
printf("%I64d
",res);
return 0;
}