題目鏈接：http://acm.ayit.edu.cn/contest/1

自我感覺這一套題的難度梯度還是很科學的。我的預期是絕大部分人做出來簡單題，少量人ac中等題。E題之前出過類似的題目，G題是一個明顯的二分，如果這兩道題都沒思路，可以肝B題。做題情況還是不容樂觀的。

分析原因可能還是大家見題比較少，尤其是新題。不能只做專題，可以經常做一下?？途W的比賽或者codeforces鍛煉一下思維。

借助本次比賽修復了網站很多bug還是很好的。

就在我寫這篇博客的時候居然有人用搜索過了E？并且耗時極少。一道構造題就這樣變成了搜索。。。

還好有人用構造過了E。

?

難度分布：

簡單題：DF
中等題：BEG
難題：AC

?

A.VN的五殺

思路：

經分析得只有敵方周圍的最多5*8個點為有效點，我們可以在這最多40個點的范圍內進行搜索。
可以將這些點分為5個集合，我們先得出一個攻擊序列，然后每次找一個集合中的兩個點，入點和出點。
可以發現入點可以取集合中距離上一個出點最近的點，并且vn在每一個集合中停留的時間一定恰好為5。
這樣我們只需要在每個集合中搜索一個出點即可。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 1005 #define inf 0x3f3f3f3f3f3f3f3f int dir[8][2]= {1,0,0,1,-1,0,0,-1,1,-1,-1,1,1,1,-1,-1}; int all[300][5],path[5]; ll stx,sty; struct node {ll x,y; } p[6],e; vector<node> vec[5]; ll ans; ll distance(ll x1,ll y1,ll x2,ll y2) {return abs(x1-x2)+abs(y1-y2); } void dfs(int step,ll lasty,ll lastx,ll s) {if(s>ans) return;if(step==5){ans=s;return;}//printf(">>%d %lld %lld %lld\n",step,lasty,lastx,s);int n=path[step];ll minn=inf;for(int i=0; i<vec[n].size(); i++){e.y=vec[n][i].y;e.x=vec[n][i].x;if(distance(e.x,e.y,lastx,lasty)<minn)minn=distance(e.x,e.y,lastx,lasty);}for(int i=0; i<vec[n].size(); i++){e=vec[n][i];dfs(step+1,e.y,e.x,s+minn+5);} } int main() {scanf("%lld%lld",&stx,&sty);for(int i=0; i<5; i++)scanf("%lld%lld",&p[i].x,&p[i].y);for(int i=0; i<5; i++){for(int j=0; j<8; j++) //找五個點周圍的點{ll ty=p[i].y+dir[j][0];ll tx=p[i].x+dir[j][1];int flag=0;for(int k=0; k<5; k++) //判斷是否重合{if(ty==p[k].y && tx==p[k].x){flag=1;break;}}e.y=ty;e.x=tx;if(!flag) vec[i].push_back(e);}}ans=inf;for(int i=0; i<5; i++) path[i]=i;do{dfs(0,sty,stx,0);}while(next_permutation(path,path+5));printf("%lld\n",ans);return 0; }

?

B.化簡方程式

思路：

可以定義一個結構體表示含x的標準項。重定義運算符。用棧先處理出乘法運算，加法運算可以直接用一個數組記錄x對應次冪下的系數，減法運算可以轉化為加法。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 105 #define inf 0x3f3f3f3f struct node {int xi,mi;node(){}node(int xx,int mm){xi=xx;mi=mm;} } p; bool cmp(node a,node b) {return a.mi>b.mi; } int xx[10005]; char str[MAXN]; node add(node a,node b) {return node(a.xi+b.xi,a.mi); } node mul(node a,node b) {return node(a.xi*b.xi,a.mi+b.mi); } stack<node> st; stack<char> fu; int main() {scanf("%s",str);for(int i=0; str[i]; i++){int d=0;int flag=0;int j=i;if(str[i]=='-'){flag=1;j++;}for(j; isdigit(str[j]); j++){d=d*10+str[j]-'0';}if(d==0) p.xi=1;else p.xi=d;if(str[j]!='x') p.mi=0;else{j++;if(str[j]!='^') p.mi=1;else{d=0;for(j=j+1; isdigit(str[j]); j++){d=d*10+str[j]-'0';}p.mi=d;}}if(flag) p.xi=-p.xi;//printf("%dx^%d %d\n",p.xi,p.mi,j);st.push(p);if(!fu.empty() && fu.top()=='*'){node a=st.top(); st.pop();node b=st.top(); st.pop();fu.pop();st.push(mul(a,b));}if(str[j]=='-') j--,fu.push('+');else if(str[j]=='+') fu.push('+');else if(str[j]=='*') fu.push('*');i=j;}memset(xx,0,sizeof xx);int maxx=0;while(!st.empty()){node top=st.top(); st.pop();xx[top.mi]+=top.xi;maxx=max(maxx,top.mi);}int out=0;for(int i=maxx;i>=1;i--){if(xx[i]==0) continue;out=1;if(xx[i]<0){if(xx[i]==-1) printf("-");else printf("%d",xx[i]);}else{if(i<maxx) printf("+");if(xx[i]>1) printf("%d",xx[i]);}printf("x");if(i>1) printf("^%d",i);}if(xx[0]!=0){if(maxx==0 || xx[0]<0) printf("%d",xx[0]),out=1;else printf("+%d",xx[0]),out=1;}if(!out) printf("0");printf("\n");return 0; }

?

C.取數游戲

思路：

可以用dpa[i]表示當前數為i時，輪到Alice取數時，Alice最終能取到的最大值。
dpb[i]表示當前數為i時，輪到Bob取數時，Alice最終能取到的最小值。
轉移方程：
dpa[i]=max( dpb[i/k]+k , max( dpb[p]+p | i-m<=p<=i-1 ) , dpb[i] ); k為i的素因子
dpb[i]=min( dpa[i/k] , min( dpa[p] | i-m<=p<=i-1 ), dpa[i]);
操作一我們可以對當前數進行分解，直接暴力枚舉質因子會超時。
操作二我們可以用兩個單調隊列維護[i-m,i-1]區間內的最小dpa和最大dpb。
更新dpa，維護que2的時候需要考慮下標的影響,下標的影響為負。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 100005 #define inf 0x3f3f3f3f int n,m,dpa[MAXN],dpb[MAXN],que1[MAXN],tmp1[MAXN],que2[MAXN],tmp2[MAXN]; int prime[MAXN]; bool is_prime[MAXN]; //返回n以內素數的個數 int sieve(int n) {int p = 0;for(int i = 0; i<= n; i++) is_prime[i] = true;is_prime[0] = is_prime[1] = false;for(int i = 2; i <= n; i++){if(is_prime[i]){prime[p++] = i;for(int j = 2 * i; j <= n; j += i) is_prime[j] = false;}}return p; } int main() {scanf("%d%d",&n,&m);dpa[0]=0;dpb[0]=0;int p=sieve(n);int head1=1,tail1=0,head2=1,tail2=0;for(int i=1; i<=n; i++){int last;dpb[i]=inf;dpa[i]=0;int d=i;for(int j=0; j<p && prime[j]<=d && prime[j]*prime[j]<=i; j++){int num=prime[j];if(d%num==0){dpb[i]=min(dpb[i],dpa[i/num]);dpa[i]=max(dpa[i],dpb[i/num]+num);while(d%num==0) d/=num;}}if(d>1)//壓縮時間{dpb[i]=min(dpb[i],dpa[i/d]);dpa[i]=max(dpa[i],dpb[i/d]+d);}while(head1<=tail1 && tmp1[head1]<i-m) head1++;while(head1<=tail1 && que1[tail1]>=dpa[i-1]) tail1--;que1[++tail1]=dpa[i-1];tmp1[tail1]=i-1;dpb[i]=min(dpb[i],que1[head1]);while(head2<=tail2 && tmp2[head2]<i-m) head2++;while(head2<=tail2 && que2[tail2]<=dpb[i-1]-i+1) tail2--;que2[++tail2]=dpb[i-1]-i+1;tmp2[tail2]=i-1;dpa[i]=max(dpa[i],que2[head2]+i);}printf("%d\n",dpa[n]);return 0; }

?

D.貪吃魚

思路：

從后往前掃，維護最大值。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 100005 int n,a[MAXN]; int main() {scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",a+i);int maxx=0,cnt=0;for(int i=n-1;i>=0;i--){if(a[i]>=maxx) maxx=a[i];else cnt++;}printf("%d\n",n-cnt);return 0; }

?

E.挑戰數獨

思路：

可以先用錯位排列構造出一個全空的數獨的解，然后3行3列的交換即可，可以發現一定會構造出解。

錯位排列的結果可以參考maze1矩陣。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long int maze1[9][9]= {{1,2,3,4,5,6,7,8,9},{4,5,6,7,8,9,1,2,3},{7,8,9,1,2,3,4,5,6},{2,3,4,5,6,7,8,9,1},{5,6,7,8,9,1,2,3,4},{8,9,1,2,3,4,5,6,7},{3,4,5,6,7,8,9,1,2},{6,7,8,9,1,2,3,4,5},{9,1,2,3,4,5,6,7,8} }; int maze[9][9]; int x,y,d; int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&y,&x,&d);x--;y--;memcpy(maze,maze1,sizeof maze1);int tt=-1;for(int i=0; i<3; i++){for(int j=0; j<3; j++){if(maze[i*3+y%3][j*3+x%3]==d){tt=i*3+j;break;}}if(tt!=-1) break;}for(int i=y/3*3; i<y/3*3+3; i++)for(int j=0; j<9; j++)swap(maze[i][j],maze[tt/3*3+i-y/3*3][j]);for(int i=x/3*3; i<x/3*3+3; i++)for(int j=0; j<9; j++)swap(maze[j][i],maze[j][tt%3*3+i-x/3*3]);for(int i=0; i<9; i++){for(int j=0; j<9; j++){if(j) printf(" ");printf("%d",maze[i][j]);}printf("\n");}}return 0; }

?

F.褻瀆

思路：

判斷是否連續。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 105 #define inf 0x3f3f3f3f int n,a[MAXN]; bool vis[MAXN]; int main() {scanf("%d",&n);memset(vis,0,sizeof vis);int maxx=0;for(int i=0;i<n;i++){scanf("%d",a+i);maxx=max(maxx,a[i]);vis[a[i]]=1;}int flag=0;for(int i=1;i<=maxx;i++){if(!vis[i]){flag=1;break;}}if(flag) puts("No");else puts("Yes");return 0; }

?

G.字母

思路：

對26個字母二分最小間隔。

check時可以用vector存字母出現的位置，然后lower_bound掃一遍即可。

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define MAXN 1000005 int n,k,ans; char str[MAXN]; vector<int> vec[30]; int check(int len) {for(int i=0;i<26;i++){if(vec[i].size()<=k) continue;int last=vec[i][0];for(int j=1;j<k;j++){int it=lower_bound(vec[i].begin(),vec[i].end(),last+len+1)-vec[i].begin();last=vec[i][it];if(last==inf) break;if(j==k-1) return 1;}}return 0; } void find(int L,int R) {if(L>=R) return;int mid=(L+R)/2;if(check(mid)){ans=mid;find(mid+1,R);}else find(L,mid); } int main() {scanf("%d%d",&n,&k);scanf("%s",str);for(int i=0;str[i];i++)vec[str[i]-'a'].push_back(i);for(int i=0;i<26;i++)vec[i].push_back(inf);ans=-1;find(0,n+1);printf("%d\n",ans);return 0; }

?

?

總結

以上是生活随笔為你收集整理的AYITOJ ROUND #1题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。