傳送門：

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的簡(jiǎn)化版，在那個(gè)題上只需要令$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$個(gè)數(shù)，讓你在其中選取$m$個(gè)，要求這$m$個(gè)數(shù)中不能有相同數(shù)字的數(shù)。現(xiàn)在問你方案數(shù)。

分析：

乍一看好像是一個(gè)組合數(shù)推公式的問題，但是我們發(fā)現(xiàn)，對(duì)于每一種數(shù)，都會(huì)存在取與不取兩種狀態(tài)，因此不好直接用組合數(shù)公式遞推。

實(shí)際上，當(dāng)我們把題目所給的所有的數(shù)都離散化之后，我們發(fā)現(xiàn)，這個(gè)問題就轉(zhuǎn)化為：給你n′n&#x27;n′種數(shù)，每種數(shù)有numinum_inumi?個(gè)，現(xiàn)在要問在這n′n&#x27;n′種數(shù)中選$k$個(gè)數(shù)的方案數(shù)。

因此我們可以把這個(gè)問題轉(zhuǎn)化成$01$背包問題。我們?cè)O(shè)$\text{dp[i][j]}$為前$i$種顏色中，有$j$種顏色已經(jīng)被取了的方案數(shù)。而對(duì)于當(dāng)前的狀態(tài)$\text{dp[i][j]}$，顯然當(dāng)前的狀態(tài)是由前$i?1$種顏色的取和不取這兩種狀態(tài)轉(zhuǎn)移過來的。因此不難有狀態(tài)轉(zhuǎn)移方程$$\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

題意：

給你一個(gè)數(shù)$k$和$b$，問你在0…2b0\dots 2^b0…2b內(nèi)，被$k$整除的數(shù)中內(nèi)的二進(jìn)制位的$1$的個(gè)數(shù)。

分析：

要統(tǒng)計(jì)一段區(qū)間內(nèi)的答案，我們比較常用的做法是通過數(shù)位$dp$。

但是在這個(gè)題中，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$b$最大為$128$，而鑒于$\text{cf}$無$\text{int128}$，因此我們無法采用狀壓的方法進(jìn)行數(shù)位$dp$。

因此我們考慮直接對(duì)二進(jìn)制數(shù)進(jìn)行數(shù)位$dp$。

我們?cè)O(shè)$\text{dp[pos][one][mo]}$代表，當(dāng)前有$pos$個(gè)二進(jìn)制位，且累計(jì)了$one$個(gè)$1$，且此時(shí)的位數(shù)的倍數(shù)是$mo$。

之后我們只需要枚舉$0/1$兩個(gè)數(shù)位，并不斷累計(jì)$\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

題意：

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

分析：

如果直接暴力搜顯然太過復(fù)雜，因此我們考慮如何進(jìn)行轉(zhuǎn)化。

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

而在這個(gè)問題中，因?yàn)椴糠贮c(diǎn)含有的是點(diǎn)權(quán)而不是邊權(quán)，因此我們考慮進(jìn)行拆點(diǎn)。我們將能設(shè)路障的點(diǎn)拆成兩個(gè)點(diǎn)，繼而使得點(diǎn)權(quán)轉(zhuǎn)化為邊權(quán)，而其他的點(diǎn)我們就分別跟超級(jí)源點(diǎn)和超級(jí)匯點(diǎn)連一條流量為無窮大的邊。之后我們只需要在我們所構(gòu)建的圖上跑最大流即為答案。

#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

復(fù)習(xí)了一邊掃描線……

在掃描線中（假設(shè)我們順著$x$軸平行的線進(jìn)行掃描），我們把一個(gè)矩形分為上下兩條線，其中下線的值為$1$，上線的值為$?1$。在我們掃描每一條線之后，我們會(huì)對(duì)當(dāng)前這條掃描線所映射的區(qū)間（即區(qū)間[x1,x2][x_1,x_2][x1?,x2?]）進(jìn)行區(qū)間更新（區(qū)間更新$1或?1$）。而每次掃描后，如果線段樹維護(hù)的某個(gè)的映射區(qū)間的標(biāo)記值大于$1$，則說明當(dāng)前當(dāng)前這個(gè)區(qū)間能夠?qū)Υ鸢赣胸暙I(xiàn)，則就將改段區(qū)間對(duì)應(yīng)的值累加，并向根部更新。最后樹頂所表示的值即為在原圖矩形中橫坐標(biāo)能貢獻(xiàn)的大小$size$，最后我們將這個(gè)大小乘上前后兩條掃描線所加的縱坐標(biāo)的大小即為對(duì)于兩條掃描線下的答案貢獻(xiàn)。

掃描線的難點(diǎn)在于離散化后各個(gè)數(shù)值之間的關(guān)系。

題意：

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

分析：

因?yàn)橛辛?#xff0c;奇數(shù)次的限制，因此我們需要考慮如何在原來的掃描線的基礎(chǔ)下進(jìn)行更改。

我們發(fā)現(xiàn)，對(duì)于掃描線所映射的區(qū)間，倘若被更新奇數(shù)次，則該段區(qū)間所對(duì)應(yīng)的值能對(duì)答案有貢獻(xiàn)；否則則沒有貢獻(xiàn)。因此我們發(fā)現(xiàn)，在這個(gè)問題中，我們只需要對(duì)標(biāo)記維護(hù)奇偶，如果當(dāng)前區(qū)間的標(biāo)記為奇，則當(dāng)前所映射的答案能夠貢獻(xiàn)，反之則不能。因此我們只需要在把之前的區(qū)間加法更新改成區(qū)間異或更新，如果$\text{lazy}$為$1$，則統(tǒng)計(jì)答案即可。

#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

題意：

給你一個(gè)矩形以及矩形外的一個(gè)點(diǎn)$p$，現(xiàn)在要以$p$為圓心，半徑為$r$，現(xiàn)在求這個(gè)圓不與矩形相交的最大的半徑。

分析：

分為三種情況進(jìn)行討論：

如果點(diǎn)$p$的$x$軸坐標(biāo)在矩形的與$x$軸平行的邊的范圍內(nèi)，則顯然答案為點(diǎn)$p$到最近的一條平行于$x$軸的距離。

如果點(diǎn)$p$的$y$軸坐標(biāo)在矩形的與$y$軸平行的邊的范圍內(nèi)，則顯然答案為點(diǎn)$p$到最近的一條平行于$y$軸的距離。

如果不屬于上述兩個(gè)條件，則答案為點(diǎn)$p$到里它最近的頂點(diǎn)的距離。

代碼：

#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

把素?cái)?shù)篩出來，模擬一下題目的內(nèi)容……然后就過了？

#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

轉(zhuǎn)載于:https://www.cnblogs.com/Chen-Jr/p/11007147.html

總結(jié)

以上是生活随笔為你收集整理的Gym 101982 （2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。