第五届武汉纺织大学ACM程序设计竞赛 个人题解（待补完）

前言：

  上周周日教练要求打的一场重现赛，时长五个小时，题目难度还行，除了部分题目前我还写不出来之外，大部分题都写完或补完了，这边给出比赛链接和我的代码（有些是队友的）和题解。

正文：

链接：第五届武汉纺织大学ACM程序设计竞赛（同步赛）_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A  广告位招租中：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int b[N];int prime[N];
int cnt;
int n, m;
void solve(int x) {for (int i = 1; i * i <= x; i++) {if (x % i == 0) {b[i]++;int u = x / i;if (u != i) {b[u]++;}}}
}int ans2, ans1;int main() {cin >> n >> m;int y = 0;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);y = max(y, a[i]);solve(a[i]);}if (m == 1) {cout << n << " " << 1 << endl;return 0;}int t = 0;for (int i = m; i <= y; i++)t = max(t, b[i]);if (t)for (int i = m; i <= y; i++) {if (b[i] == t) {ans2 = i;bool flag = 0;for (int j = i * 2; j <= y; j += i) {if (b[j] == t) {ans2 = j;flag = 1;break;}}if (!flag) {ans2 = i;break;}}}cout << t << " " << ans2 << endl;
}

和队友讨论出来的做法，对输入的每一个数，我们算出他的因子（大于m）并对这些因子个数计数，之后重小因子枚举到最后，如果有更大的因子满足最多的数我们就更新答案，如果没有大于m的因子就输出00。

B MEX of MEXes：

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int a[N];
int b[N];int main() {int n;cin >> n;if (n == 1) {cout << 1;return 0;}if (n == 2) {cout << 4;return 0;}int l, r;for (int i = 1; i <= n; i++) {cin >> a[i];b[a[i]] = i;if (a[i] == 1)l = i;if (a[i] == 2)r = i;}if (l > r)swap(l, r);//cout << l << " " << r << endl;for (int i = 3; i <= n; i++) {int loca = b[i];//cout << i << " " << loca << endl;if (loca > l && loca < r) {cout << i;return 0;} else {l = min(l, loca);r = max(r, loca);continue;}}cout<<n+2;}

  首先如果n=1，那么数组b为{2}，那么最后结果为1。如果n>1，那么数组b一定包含1。很自然的，我们想数组b是否包含2，是否包含3，是否包含4......对于是否包含k来说，我们只需要找到数组a的一个非空连续子数组包含1到k-1且不包含k，就说明数组b包含k。那么我们找到包含1到k-1的长度最小的子数组，然后判断里面是否包含k即可。整个过程可以使用双指针实现，维护一个区间，区间初始左右端点为1的位置，再找到2的位置并更新区间左右端点，判断区间内是否包含3，再找3的位置......若此时考虑x的位置，那么区间更新后如果区间包含了x+1，那么就说明数组b中不可能存在x+1，最后答案即为x+1。特殊地，如果考虑了1到n都符合后，那么此时数组b {1,2,3...n+1}，最后答案为n+2。

C 战斗时回复:

#include<bits/stdc++.h>
using namespace std;
int main(){double T,h,t,n;cin>>T>>h>>t>>n;if(h/T>=n/t)cout<<"kirito";else cout<<"hangeki";return 0;
}

水题。

D 小太阳的帕鲁世界1：

#include<bits/stdc++.h>
using namespace std;
string s[2005];
bool book[2005][2005];
int ans[2005][2005];
int n,m;
void dfs(int x,int y,int z){if(y>=m||y<0||x>=n||x<0)return;ans[x][y]=z;if(s[x][y]=='L')dfs(x,y+1,z+1);if(s[x][y]=='R')dfs(x,y-1,z+1);   if(s[x][y]=='U')dfs(x+1,y,z+1);if(s[x][y]=='D')dfs(x-1,y,z+1);
}
int main(){cin>>n>>m;memset(ans,-1,sizeof(ans));for(int i=0;i<n;i++){cin>>s[i];}dfs(n-1,m-1,0);for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<ans[i][j]<<" ";}cout<<endl;}return 0;
}

简单bfs，队友用了bfs也能过，代码见下

#include <bits/stdc++.h>
using namespace std;const int N = 2010;
char maze[N][N];
int dis[N][N];
bool vis[N][N];
int n, m;int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
typedef pair<int, int> PII;
map<char, PII> ma;void bfs() {queue<PII> q;q.push({n, m});vis[n][m] = 1;dis[n][m] = 0;while (q.size()) {auto t = q.front();q.pop();int x = t.first, y = t.second;char instruct = maze[x][y];auto tt = ma[instruct];int dx = tt.first + x, dy = tt.second + y;//	cout << dx << " " << dy << endl;dis[dx][dy] = dis[x][y] + 1;vis[dx][dy] = 1;if (dx >= 1 && dx <= n && dy >= 1 && dy <= m)q.push({dx, dy});}return;}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> maze[i][j];}}ma['U'] = {1, 0};ma['D'] = {-1, 0};ma['R'] = {0, -1};ma['L'] = {0, 1};bfs();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (vis[i][j])cout << dis[i][j] << " ";elsecout << "-1 ";}cout << endl;}}

E 小太阳的帕鲁世界2(待补):

F 又掉分了：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){int x,n;cin>>x>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>x)x+=(a[i]-x)/2;}cout<<x;return 0;
}

贪心，能上分就打，否者不打。

G Birusu的公园（待补）：

H 被诅咒的宝藏：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll a[N],b[N];ll n,s;
bool check(int x){ll cnt=0;for(int i=1;i<=n;i++){b[i]=a[i]+i*x;}sort(b+1,b+n+1);for(int i=1;i<=x;i++){cnt+=b[i];}if(cnt>s)return 1;return 0;
}
int main(){ll ans=0;cin>>n>>s;for(int i=1;i<=n;i++)cin>>a[i];ll l=1,r=n,mid;while(l<r){mid=l+r+1>>1;if(check(mid))r=mid-1;else l=mid;}for(int i=1;i<=n;i++){b[i]=a[i]+i*l;}sort(b+1,b+n+1);for(int i=1;i<=l;i++){ans+=b[i];}cout<<r<<" "<<ans<<endl;  return 0;
}

先用二分找出最多能拿几个物品，这边要注意随着所拿物品数量不同每个物品的代价都会不一样，所以每次判断都要对相应的代价排序，之后在根据数量算出最小重量。

I 决定命运的博弈：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){ll n;cin>>n;if(n==1)cout<<"Dbqjubmjtn";else cout<<"Tpdjbmjtn";return 0;
}

我一开始想的是只有n=1时d能赢，刚刚发现题目条件n>=2 ,所以t是必胜的（只要先手拿不完，后手就能一下拿完）。

J 52Hz的minmax区间（easy）（待补）：

K 52Hz的minmax区间（hard）（待补）：

这两道题都没啥想法。

L Kaiou的笑话：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int el[N],er[N],al[N],ar[N];
int main(){int m;cin>>m;string s;int l=-1,r=-1;int ans=10000000;cin>>s;for(int i=0;i<m;i++){if(s[i]=='t')l=i;if(s[i]=='e'){el[i]=l;	}}for(int i=m-1;i>=0;i--){if(s[i]=='n')r=i;if(s[i]=='e'){er[i]=r;	}}l=-1,r=-1;for(int i=0;i<m;i++){if(s[i]=='h')l=i;if(s[i]=='a'){al[i]=l;	}}for(int i=m-1;i>=0;i--){if(s[i]=='n')r=i;if(s[i]=='a'){ar[i]=r;	}}for(int i=0;i<m;i++){if(s[i]=='e'&&el[i]!=-1&&er[i]!=-1){ans=min(ans,er[i]-el[i]-2);}if(s[i]=='a'&&al[i]!=-1&&ar[i]!=-1){ans=min(ans,ar[i]-al[i]-2);}}if(ans==10000000)cout<<-1;else cout<<ans;return 0;
}

记入下中间那个字母左右最近的那个相应字母的位置最后求出最小距离就为答案。

M 大生：

#include<bits/stdc++.h>
using namespace std;
int main(){cout<<"我不知道";return 0;
}

好像输出什么都可以。

后记：

  这个比赛比了一整个下午，刚比完饭还没吃就被拉去上课了，整个人困得很，不过这场比赛的题确实适合我这种算法比赛的新人，待补的题在之后一定补完（什么时候就不知道了）。