Gym 101982 （2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) )

傳送門：

Problem A

溫暖的簽到題

#include<bits/stdc++.h>
using namespace std;
const int maxn=1007;
char s1[maxn],s2[maxn];
int main(){ios::sync_with_stdio(false);cin.tie(0);int n,k,sum0=0,sum1=0;cin>>k>>s1>>s2;n=strlen(s1);for (int i=0;i<n;i++)if (s1[i]==s2[i]) sum1++;else sum0++;int ans=0;if (k<=sum1) ans=k+sum0;else ans=sum1+sum0-(k-sum1);cout<<ans<<endl;return 0;
}

---

Problem B

莫比烏斯反演大原題！

BZOJ2301的簡化版，在那個題上只需要令$k=1$

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000007;
bool check[maxn+10];
int prime[maxn+10];
int mu[maxn+10];
typedef long long ll;
void Moblus(){for(int i=0;i<=maxn;i++){check[i]=false;}mu[1]=1;int tot=0;for(int i=2;i<=maxn;i++){if(!check[i]){prime[tot++]=i;mu[i]=-1;}for(int j=0;j<tot;j++){if(i*prime[j]>maxn) break;check[i*prime[j]]=true;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}else{mu[i*prime[j]]=-mu[i];}}}
}
int sum[maxn+10];
ll solve(int n,int m){ll ans=0;if(n>m) swap(n,m);for(int i=1,la=0;i<=n;i=la+1){la=min(n/(n/i),m/(m/i));ans+=(ll)(sum[la]-sum[i-1])*(n/i)*(m/i);}return ans;
}
int main()
{Moblus();sum[0]=0;for(int i=1;i<=maxn;i++){sum[i]=sum[i-1]+mu[i];}int a,b,c,d,k;scanf("%d%d%d%d",&a,&b,&c,&d);k=1;ll ans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve(b/k,(c-1)/k)+solve((a-1)/k,(c-1)/k);printf("%lld\n",ans);return 0;
}

---

Problem C

題意：

給你$n$個數，讓你在其中選取$m$個，要求這$m$個數中不能有相同數字的數。現在問你方案數。

分析：

乍一看好像是一個組合數推公式的問題，但是我們發現，對于每一種數，都會存在取與不取兩種狀態，因此不好直接用組合數公式遞推。

實際上，當我們把題目所給的所有的數都離散化之后，我們發現，這個問題就轉化為：給你n′n'n′種數，每種數有numinum_inumi?個，現在要問在這n′n'n′種數中選$k$個數的方案數。

因此我們可以把這個問題轉化成$01$背包問題。我們設$\text{dp[i][j]}$為前$i$種顏色中，有$j$種顏色已經被取了的方案數。而對于當前的狀態$\text{dp[i][j]}$，顯然當前的狀態是由前$i?1$種顏色的取和不取這兩種狀態轉移過來的。因此不難有狀態轉移方程$$\text{dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]}$$

代碼：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+7;
typedef long long ll;
const int mod=998244353;
ll dp[maxn][maxn];
unordered_map<int,int>mp;
int a[maxn];
int main(){// freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);int n,k,x,cnt=0;cin>>n>>k;for (int i=1;i<=n;i++) {cin>>x;if (!mp.count(x)) mp[x]=++cnt,a[cnt]=1;else a[mp[x]]++;}dp[0][0]=1;for (int i=1;i<=cnt;i++) dp[i][0]=1;for (int i=1;i<=cnt;i++){for (int j=1;j<=k;j++) {dp[i][j]=(dp[i][j]+dp[i-1][j-1]*a[i]%mod)%mod;dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;}}cout<<dp[cnt][k]<<endl;return 0;
}

---

Problem D

題意：

給你一個數$k$和$b$，問你在0…2b0\dots 2^b0…2b內，被$k$整除的數中內的二進制位的$1$的個數。

分析：

要統計一段區間內的答案，我們比較常用的做法是通過數位$dp$。

但是在這個題中，因為$b$最大為$128$，而鑒于$\text{cf}$無$\text{int128}$，因此我們無法采用狀壓的方法進行數位$dp$。

因此我們考慮直接對二進制數進行數位$dp$。

我們設$\text{dp[pos][one][mo]}$代表，當前有$pos$個二進制位，且累計了$one$個$1$，且此時的位數的倍數是$mo$。

之后我們只需要枚舉$0/1$兩個數位，并不斷累計$\text{dfs(pos-1,one+i,(mo*2+i)\%k)}$即為答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
ll dp[130][130][1007],p[130];
bool a[130];
int b,k;
ll dfs(int pos,int one,int mo){if (pos==-1) {if (mo==0) return one;return 0;}if (dp[pos][one][mo]!=-1) return dp[pos][one][mo];ll res=0;for (int i=0;i<=1;i++){res=(res+dfs(pos-1,one+i,(mo*2+i)%k))%mod;}dp[pos][one][mo]=res;return res;
}
int main()
{//freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cin>>k>>b;memset(dp,-1,sizeof dp);for (int i=0;i<b;i++) a[i]=1;cout<<dfs(b-1,0,0)<<endl;return 0;
}

---

Problem E

題意：

在一個$n?m$的平面圖中，一個匪徒位于(xB,yB)(x_B,y_B)(xB?,yB?)處，現在他想要逃出這個圖。現在警察想要設置路障阻礙匪徒逃跑。現在平面圖中有$k$種地形，在第$i$種地形布置路障需要花費valival_ivali?元。現在問你最少花費多少錢才能阻止匪徒逃跑。

分析：

如果直接暴力搜顯然太過復雜，因此我們考慮如何進行轉化。

我們發現，這個題的的目的是阻止匪徒逃跑，換句話說，就是阻止匪徒走到邊界點。即，讓倘若我們把匪徒看成源點，邊界點看作匯點，則我們現在想要做的即是求出切斷源點與匯點的最小花費。而這個即是最小割。

而在這個問題中，因為部分點含有的是點權而不是邊權，因此我們考慮進行拆點。我們將能設路障的點拆成兩個點，繼而使得點權轉化為邊權，而其他的點我們就分別跟超級源點和超級匯點連一條流量為無窮大的邊。之后我們只需要在我們所構建的圖上跑最大流即為答案。

#include <bits/stdc++.h>
#define maxn 10005
using namespace std;
struct Node{int to,next,val,w;
}q[maxn];
int head[maxn],cur[maxn],cnt,dep[maxn],vis[maxn],sp,tp;
const int INF=0x3f3f3f3f;
void add_edge(int from,int to,int val){q[cnt].to=to;q[cnt].val=val;q[cnt].next=head[from];head[from]=cnt++;q[cnt].to=from;q[cnt].val=0;q[cnt].next=head[to];head[to]=cnt++;
}
bool bfs(){int vis[maxn];memset(dep,INF,sizeof(dep));memset(vis,0,sizeof(vis));queue<int>que;dep[sp]=0;que.push(sp);while(!que.empty()){int x=que.front();que.pop();vis[x]=0;for(int i=head[x];i!=-1;i=q[i].next){int to=q[i].to;if(dep[to]>dep[x]+1&&q[i].val){dep[to]=dep[x]+1;if(vis[x]==0)que.push(to);vis[to]=1;}}}if(dep[tp]!=INF) return 1;else return 0;
}
int dfs(int u,int flow){int rlow=0;if(u==tp)return flow;for(int i=cur[u];i!=-1;i=q[i].next){int d=q[i].to;cur[u]=1;if(q[i].val&&dep[d]==dep[u]+1){if(rlow=dfs(d,min(flow,q[i].val))){q[i].val-=rlow;q[i^1].val+=rlow;return rlow;}}}return 0;
}
int Dinic(){int total=0,tt;int lowflow=0;while(bfs()){memcpy(cur,head,sizeof(head));while(lowflow=dfs(sp,INF)) total+=lowflow;}return total;
}
int a[maxn];
char str[maxn][maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int main()
{int n,m,k;memset(head,-1,sizeof(head));cnt=0;scanf("%d%d%d",&m,&n,&k);for(int i=0;i<n;i++){scanf("%s",str[i]);}for(int i=0;i<k;i++){scanf("%d",&a[i]);}sp=2*n*m+100,tp=sp+1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){int u=i*m+j;if(str[i][j]=='.'||str[i][j]=='B')add_edge(u,u+n*m,INF);else add_edge(u,u+n*m,a[str[i][j]-'a']);for(int k=0;k<4;k++){int ii=i+dx[k];int jj=j+dy[k];if(ii>=n||ii<0||jj>=m||jj<0)add_edge(u+n*m,tp,INF);else add_edge(u+n*m,(ii*m+jj),INF);}if(str[i][j]=='B')add_edge(sp,u,INF);}}int res=Dinic();if(res>=INF) puts("-1");else cout<<res<<endl;return 0;
}

---

Problem F

復習了一邊掃描線……

在掃描線中（假設我們順著$x$軸平行的線進行掃描），我們把一個矩形分為上下兩條線，其中下線的值為$1$，上線的值為$?1$。在我們掃描每一條線之后，我們會對當前這條掃描線所映射的區間（即區間[x1,x2][x_1,x_2][x1?,x2?]）進行區間更新（區間更新$1或?1$）。而每次掃描后，如果線段樹維護的某個的映射區間的標記值大于$1$，則說明當前當前這個區間能夠對答案有貢獻，則就將改段區間對應的值累加，并向根部更新。最后樹頂所表示的值即為在原圖矩形中橫坐標能貢獻的大小$size$，最后我們將這個大小乘上前后兩條掃描線所加的縱坐標的大小即為對于兩條掃描線下的答案貢獻。

掃描線的難點在于離散化后各個數值之間的關系。

題意：

給你$n$個矩形，讓你求這$n$個矩形中的被覆蓋的次數為奇數的面積并。

分析：

因為有了，奇數次的限制，因此我們需要考慮如何在原來的掃描線的基礎下進行更改。

我們發現，對于掃描線所映射的區間，倘若被更新奇數次，則該段區間所對應的值能對答案有貢獻；否則則沒有貢獻。因此我們發現，在這個問題中，我們只需要對標記維護奇偶，如果當前區間的標記為奇，則當前所映射的答案能夠貢獻，反之則不能。因此我們只需要在把之前的區間加法更新改成區間異或更新，如果$\text{lazy}$為$1$，則統計答案即可。

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
struct Node{int x1,x2,y,w;Node(){}Node(int _x1,int _x2,int _y,int _w){x1=_x1,x2=_x2,y=_y,w=_w;}bool operator <(const Node &b)const{return y<b.y;}
}q[maxn*2];
struct ST{int sum,lazy;
}tr[maxn<<2];
void push_up(int rt){tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
}
int S[maxn];
void push_down(int l,int r,int rt){if(tr[rt].lazy!=0){int mid=(l+r)>>1;tr[rt<<1].sum=S[mid]-S[l-1]-tr[rt<<1].sum;tr[rt<<1|1].sum=S[r]-S[mid]-tr[rt<<1|1].sum;tr[rt<<1].lazy^=1;tr[rt<<1|1].lazy^=1;tr[rt].lazy=0;}
}
void update(int L,int R,int l,int r,int rt){if(L<=l&&R>=r){tr[rt].sum=S[r]-S[l-1]-tr[rt].sum;tr[rt].lazy^=1;return ;}push_down(l,r,rt);int mid=(l+r)>>1;if(L<=mid) update(L,R,l,mid,rt<<1);if(R>mid) update(L,R,mid+1,r,rt<<1|1);push_up(rt);
}
int main()
{int n;scanf("%d",&n);int tot=0,cnt=0;for(int i=1;i<=n;i++){int x1,y1,x2,y2;if(x1>x2) swap(x1,x2);if(y1>y2) swap(y1,y2);scanf("%d%d%d%d",&x1,&y1,&x2,&y2);q[++cnt]=Node(x1,x2,y1,1);q[++cnt]=Node(x1,x2,y2,-1);S[++tot]=x1;S[++tot]=x2;}sort(q+1,q+1+cnt);sort(S+1,S+1+tot);tot=unique(S+1,S+1+tot)-S-1;long long res=0;for(int i=1;i<=cnt;i++){int l=lower_bound(S+1,S+1+tot,q[i].x1)-S;int r=lower_bound(S+1,S+1+tot,q[i].x2)-S;if(l<=r) update(l+1,r,1,tot,1);if(i!=cnt){res+=1ll*tr[1].sum*(q[i+1].y-q[i].y);}}printf("%lld\n",res);return 0;
}

---

Problem G

題意：

給你一個矩形以及矩形外的一個點$p$，現在要以$p$為圓心，半徑為$r$，現在求這個圓不與矩形相交的最大的半徑。

分析：

分為三種情況進行討論：

1. 如果點$p$的$x$軸坐標在矩形的與$x$軸平行的邊的范圍內，則顯然答案為點$p$到最近的一條平行于$x$軸的距離。
2. 如果點$p$的$y$軸坐標在矩形的與$y$軸平行的邊的范圍內，則顯然答案為點$p$到最近的一條平行于$y$軸的距離。
3. 如果不屬于上述兩個條件，則答案為點$p$到里它最近的頂點的距離。

代碼：

#include <bits/stdc++.h>
using namespace std;
double eps=1e-8;
int sgn(double x){if(fabs(x)<eps) return 0;if(x<0) return -1;else return 1;
}
struct Point{double x,y;Point(){}Point(double _x,double _y){x=_x,y=_y;}double operator ^(const Point &b)const{return x*b.y-y*b.x;}double operator *(const Point &b)const{return x*b.x+y*b.y;}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}double distance(Point p){return hypot(x-p.x,y-p.y);}
};
struct Line{Point s,e;Line(){}Line(Point _s,Point _e){s=_s;e=_e;}double length(){return s.distance(e);}double dispointtoline(Point p){return fabs((p-s)^(e-s))/length();}
};
int main()
{//freopen("in.txt","r",stdin);Point a,b,c;scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);Line l[4];l[0]=Line(b,Point(b.x,c.y));l[1]=Line(b,Point(c.x,b.y));l[2]=Line(c,Point(b.x,c.y));l[3]=Line(c,Point(c.x,b.y));double res;double x1=min(l[1].s.x,l[1].e.x);double x2=max(l[1].s.x,l[1].e.x);double y1=min(l[0].s.y,l[0].e.y);double y2=max(l[0].s.y,l[0].e.y);if(a.x<=x2&&a.x>=x1){res=1e18;res=min(res,l[1].dispointtoline(a));res=min(res,l[2].dispointtoline(a));}else if(a.y<=y2&&a.y>=y1){res=1e18;res=min(res,l[0].dispointtoline(a));res=min(res,l[3].dispointtoline(a));}else{double tmp=a.distance(b);double tmp1=a.distance(c);double tmp2=a.distance(Point(b.x,c.y));double tmp3=a.distance(Point(c.x,b.y));res=min(tmp,min(tmp1,min(tmp2,tmp3)));}printf("%.3f\n",res);return 0;
}

---

Problem H

把素數篩出來，模擬一下題目的內容……然后就過了？

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int prime[maxn+1];
bool p[maxn+1];
void getPrime(){memset(prime,0,sizeof(prime));for(int i=2;i<=maxn;i++){if(!prime[i]) prime[++prime[0]]=i,p[i]=1;for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[prime[j]*i]=1;if(i%prime[j]==0) break;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);getPrime();int n;cin>>n;int ans=0,x=n;while (x>=4){ans++;for (int j=x;j>=2;j--)if (p[j]&&p[x-j]) {x=j-x+j;break;}}cout<<ans<<endl;return 0;
}

---

Problem I

---

Problem J

溫暖的簽到題

代碼：

#include <bits/stdc++.h>
using namespace std;int main()
{int n,s;cin>>n>>s;int maxx=0;for(int i=1;i<=n;i++){int num;cin>>num;maxx=max(maxx,num);}maxx*=s;int res=(maxx+999)/1000;cout<<res<<endl;
}

---

Problem K

---

Problem L

溫暖的簽到題+1

#include <bits/stdc++.h>
using namespace std;
const int maxn=1007;
int a[maxn],b[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,ans=-1;cin>>n;for (int i=1;i<=n;i++) cin>>a[i]>>b[i];for (int i=0;i<=n;i++){int sum=0;for (int j=1;j<=n;j++)if (a[j]<=i&i<=b[j]) sum++;if (i==sum) ans=max(ans,i);}cout<<ans<<endl;return 0;
}

---

Problem M