AtCoder Beginner Contest 450（ABC450）
A - 3,2,1,GO
输出即可。
点击查看代码
//连胡闹都是甜，爱你像诗篇，最动人心弦~
#include<bits/stdc++.h>
using namespace std;
int n;
signed main(){
cin >> n;
for(int i = n;i > 1;-- i)
cout << i << ',';
cout << 1;
return 0;
}
B - Split Ticketing
枚举\(a\)，\(b\)和\(c\)，判断一下，如果符合条件就直接输出Yes，如果到最后也没找着符合条件的就输出No。
点击查看代码
//连胡闹都是甜，爱你像诗篇，最动人心弦。
#include<bits/stdc++.h>
using namespace std;
int n;
int v[105][105];
signed main(){
cin >> n;
for(int i = 1;i < n;++ i)
for(int j = i+1;j <= n;++ j)
cin >> v[i][j];
for(int a = 1;a <= n;++ a){
for(int b = a+1;b <= n;++ b){
for(int c = b+1;c <= n;++c){
if(v[a][b]+v[b][c] < v[a][c]){
cout << "Yes";
return 0;
}
}
}
}
cout << "No";
return 0;
}
C - Puddles
先考虑如果贴着边界的那些白色联通块也算怎么办？枚举每一个位置，如果这个位置是.，就从这个位置开始\(bfs\)，遍历所有和它相通的.的位置，然后把这些位置都赋为#（防止重复遍历），那么遍历到的这些位置就是一个白色联通块，答案加一即可。
现在的问题是贴着边界的不算。那么我们从所有边界位置开始\(bfs\)一遍，也是把所有和它相通的.的位置赋为#，但是答案不要加一，因为贴着边界的不算。
那么就结束了，注意在\(bfs\)时某个位置一入队就要把它改成#，否则会重复遍历会\(TLE\)。
点击查看代码
//连胡闹都是甜，爱你像诗篇，最动人心弦。
#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[1005][1005];
int dx[] = {0,1,-1,0,0};
int dy[] = {0,0,0,1,-1};
void bfs(int x,int y){
if(c[x][y] != '.') return;
queue<pair<int,int> > q;
q.push({x,y});
c[x][y] = '#';
while(!q.empty()){
auto [a,b] = q.front();q.pop();
for(int i = 1;i <= 4;++ i){
int aa = a+dx[i];
int bb = b+dy[i];
if(aa >= 1&&aa <= n&&bb >= 1&&bb <= m&&c[aa][bb] == '.'){
q.push({aa,bb});
c[aa][bb] = '#';
}
}
}
}
signed main(){
cin >> n >> m;
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= m;++ j)
cin >> c[i][j];
for(int i = 1;i <= m;++ i)
bfs(1,i),bfs(n,i);
for(int i = 1;i <= n;++ i)
bfs(i,1),bfs(i,m);
int ans = 0;
for(int i = 2;i < n;++ i)
for(int j = 2;j < m;++ j){
if(c[i][j] == '.'){
ans++;
bfs(i,j);
}
}
cout << ans;
return 0;
}
D - Minimize Range
不是啊喂，这题咋灵机一动就想出来了？？？
首先可以发现，虽然题目说只能加\(K\)，但是减\(K\)也是可以的，为啥？我们发现最终要求的东西是一个相对大小，也就是如果所有数都加上同一个数，那么答案是不会改变的。所以如果我们给其他的所有数加上\(K\)，就相当于给一个数减去\(K\)了。
那么，我们先让所有数对\(K\)取余，也就是一直减\(K\)直到不能减为止，再从小到大排个序，这样会比较好考虑一些。然后呢？我们考虑把多少个数加到\(K\)以上，这时我们发现我们一定会把前\(x\)个连续的加到\(K\)以上（为什么？自己想一下），那么这时最大数是\(a_x+K\)，最小数是\(a_{x+1}\)，枚举\(x\)算一下就行了。
点击查看代码
//连胡闹都是甜，爱你像诗篇，最动人心弦。
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[200005];
signed main(){
cin >> n >> k;
for(int i = 1;i <= n;++ i)
cin >> a[i],a[i] %= k;
sort(a+1,a+1+n);
int ans = a[n]-a[1];
for(int i = 1;i < n;++ i)
ans = min(ans,a[i]+k-a[i+1]);
cout << ans;
return 0;
}
E - Fibonacci String
自己想出来了做法，结果因为处理不当多了个\(log\)，超时了。。。
可以发现，\(\forall i \geq 3\)都有\(S_{i-1}\)是\(S_i\)的前缀。
而且，\(S_i\)的长度即为斐波那契数列的第\(i\)项。其实，斐波那契数列第\(100\)项左右就已经超过了\(10^18\)次方了，为了严谨，我们设\(S_n\)是第一个长度超过\(10^18\)的字符串。
有了这两个发现，我们再次发现完全没必要在\(S_{10^18}\)里面求东西，因为\(S_n\)一定是\(S_{10^18}\)的前缀，我们只需要在\(S_n\)里求前\(a\)个字符中有多少个字符\(c\)即可。
我们定义一个函数\(f(k,a,c)\)代表\(S_k\)的前\(a\)个字符中有多少个字符\(c\)，那么有（以下的\(len_i\)代表\(S_i\)的长度）：
1.\(k=1\)时，即为\(x\)的前\(a\)个字符中有多少个字符\(c\)；
2.\(k=2\)时，即为\(y\)的前\(a\)个字符中有多少个字符\(c\)；
3.\(a \leq len_{k-1}\)时，返回\(f(k-1,a,c)\)；
4.\(a > len_{k-1}\)时，返回\(f(k-2,a-len_{k-1},c)\)和\(S_k\)中字符\(c\)的个数的和。
后两个自己想一下为什么。
那么我们都需要\(O(1)\)查什么呢？
1.\(x\)的前\(a\)个字符中有多少个字符\(c\)；
2.\(y\)的前\(a\)个字符中有多少个字符\(c\)；
3.\(S_k\)中字符\(c\)的个数。
前两个用一个前缀和求，第三个递推一下，\(S_k\)中字符\(c\)的个数就是\(S_{k-1}\)中字符\(c\)的个数加\(S_{k-2}\)中字符\(c\)的个数（对应代码中的\(gs\)数组，可以看一下代码）。
那么我们可以在\(O(100)\)的复杂度内求\(f\)了，那么一个询问就可以转化为\(f(n,r,c)-f(n,l-1,c)\)了。
总复杂度\(O(10^7)\)，貌似跑得还挺快。
点击查看代码
//连胡闹都是甜，爱你像诗篇，最动人心弦。
#include<bits/stdc++.h>
#define int long long
using namespace std;
string x,y;
int len[105],n;
int gs[30][105];
int qx[30][10005];
int qy[30][10005];
int get(int k,int a,int c){
//S[k]前a个字符中字符c的个数
if(k == 1) return qx[c][a-1];
if(k == 2) return qy[c][a-1];
if(a <= len[k-1]) return get(k-1,a,c);
else return gs[c][k-1]+get(k-2,a-len[k-1],c);
}
signed main(){
cin >> x >> y;
len[1] = x.length();
len[2] = y.length();
for(int i = 0;i < len[1];++ i){
gs[x[i]-'a'][1]++;
for(int j = 0;j < 26;++j)
qx[j][i] = qx[j][i-1];
qx[x[i]-'a'][i]++;
}
for(int i = 0;i < len[2];++ i){
gs[y[i]-'a'][2]++;
for(int j = 0;j < 26;++j)
qy[j][i] = qy[j][i-1];
qy[y[i]-'a'][i]++;
}
for(n = 3;n <= 100;++ n){
for(int j = 0;j < 26;++j)
gs[j][n] = gs[j][n-1]+gs[j][n-2],
gs[j][n] = gs[j][n-1]+gs[j][n-2];
len[n] = len[n-1]+len[n-2];
if(len[n] > 1e18) break;
}
int _;cin >> _;
while(_--){
int l,r;char c;
cin >> l >> r >> c;
cout << get(n,r,c-'a')-get(n,l-1,c-'a') << '\n';
}
return 0;
}
浙公网安备 33010602011771号