比赛地址添加链接描述
A - Piling Up
算法： 模拟
题目大意
在 AtCoder 竞赛平台中，用户的等级通过正整数分数表示，并根据分数显示相应数量的 ^ 符号。分数与 ^ 符号显示的规则如下：
当分数在 1 到 99（包括 99）之间时，显示一个 ^。
当分数在 100 到 199（包括 199）之间时，显示两个 ^。
当分数在 200 到 299（包括 299）之间时，显示三个 ^。
当分数在 300 到 399（包括 399）之间时，显示四个 ^。
高桥当前的分数是 R，题目保证 R 是一个介于 1 到 299 之间的整数。
任务是求出高桥需要增加的最小分数，使得他的 ^ 符号显示数量增加一个。
算法思路
重点就是读懂题目，基本没什么思路，只需要模拟即可。
代码
#include<stdio.h>
#define ll long long
const int N = 3e5+7;
void slove() {
int n;
cin>>n;
if(n<=99) cout<<100-n;
else if(n<=199) cout<<200-n;
else if(n<=299) coiut<<300-n;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slove();
return 0;
}
B - Japanese Cursed Doll
算法
题目大意
算法思路
代码
B - Japanese Cursed Doll
算法：贪心+模拟
题目大意
有 N 个人，每个人当前的头发长度为 Li（长度单位为厘米）。每个人的头发每天都会均匀增长 1 厘米。
给定两个整数 T 和 P，分别代表特定的头发长度阈值和人数阈值。
任务是找出从某天开始，头发长度至少为 T 厘米的人数首次达到或超过 P 人的那一天的天数。如果一开始至少有 P 人的头发长度已经达到或超过 T 厘米，则输出的天数应该是 0。
算法思路
因为数据并不是很大，只需要先排序，然后在进行模拟即可。
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
using namespace std;
int a[N];
void slove() {
int n,t,p;
cin>>n>>t>>p;
for(int i=1;i<=n;++i) cin>>a[i];
sort(a+1,a+n+1,greater<int>());
cout<<max(0,t-a[p]);
return;
}
int main(){
slove();
return 0;
}
C - Avoid K Palindrome 2
算法：dfs+字符串操作+模拟
题目大意
给定一个由小写英文字母组成的字符串 S，其长度为 N。
要求计算通过置换（排列）字符串 S 中的字符后，所得到的字符串中不包含任何长度为 K 的回文子串的排列方式有多少种。
一个字符串被认为是长度为 K 的回文，如果它正读和反读都一样，并且这个回文子串的长度不超过 N-K+1。
如果通过置换字符能够得到不包含长度为 K 的回文子串的字符串，这样的置换方式算作一个有效结果。
任务是计算所有可能的置换中，满足条件的有效置换有多少种
算法思路
因为N的数据很小，那么我们可以对S进行全排列，然后对全排列以后的字符串进行判断，看是否存在长度为K的回文子串。
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
using namespace std;
map<string,int> mp;
int tp[15];
string s;
int n,k;
ll ans = 0;
bool check(string ts) {
if(mp[ts]==1) return true;
mp[ts] = 1;
for(int i=0;i<ts.size()-k/2;++i) {
int flag = 0;
for(int j=0;j<k/2;j++) {
if(ts[i+j]!=ts[i+k-j-1]) flag = 1;
}
if(flag == 0) return true;
}
return false;
}
void dfs(int x,string ts) {
if(x==n) {
// cout<<ts;
if(!check(ts)) ans++;
return;
}
for(int i=0;i<s.size();++i) {
if(tp[i]==0) {
tp[i]=1;
dfs(x+1,ts+s.substr(i,1));
tp[i]=0;
}
}
return;
}
void slove() {
cin>>n>>k;
cin>>s;
dfs(0,"");
cout<<ans;
return;
}
int main(){
slove();
return 0;
}
D - Palindromic Number
算法：贪心+模拟
题目大意
定义了一个特殊的数，称为回文数，它的十进制表示法（不包含前导零）正读和反读是一样的。
给出一些例子，如 363、12344321 和 0 都是回文数。
任务是求第 N 小的回文数。这意味着你需要找到一个数，它是所有回文数中第 N 个按数值从小到大排列的数。
算法思路
这题的思路比较巧，题目要求我们找到第N个回文数，因为第N个回文串本身数据比较大，超出了long long的范围，肯定无法通过常规方法进行输出，但我们可以通过一位一位打印输出。
例如46，我们可以知道长度为1的数字有10个(0,1,2,3,4,5,6,7,8,9)，长度为2的数字有9个(11,22,33,44,55,66,77,88,99)，又因为长度为3的回文数必须保证头尾相同，那么头尾为1的回文数有(101,111,121,131,141,151,161,171,181,191)，从1-9都会有10个，所以我们能推出头尾是3，然后又是10个里面的第几个，就可以推出6，然后打印出来即可。
重点就是理解代码。
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
const int N = 1e5+7;
const ull M = 1e18;
using namespace std;
//t存放的对应位数有多少回文数
ull t[107] = {0,10,9};
//tt存放的是包含前导0情况的回文数个数
ull tt[107] = {0,10,10};
//tans存放的是前缀和
ull tans[107] = {0,10,19};
ull ans = 19;
void slove() {
// for(int i=1;i<=len;++i) cout<<t[i]<<endl;
// cout<<len;
ull n;
cin>>n;
ull i;
//i确定所求的数是几位数
for(i=1; i<=50; ++i) {
if(n<=tans[i]) break;
}
// cout<<i;
vector<int> ve;
ull tn = n - tans[i-1];
// cout<<tn<<endl;
//一位一位处理
for(ull ii=1; ii<=int(ceil(1.0*i/2)); ++ii) {
//处理第几位数
int tsz = i-(ii-1)*2;
if(tsz == 1 || tsz == 2) {
ve.push_back(tn-1);
} else {
if(ii==1) {
if(tn%tt[tsz-2]==0) {
ve.push_back(tn/tt[tsz-2]);
} else ve.push_back(tn/tt[tsz-2]+1);
} else {
if(tn%tt[tsz-2]==0) {
ve.push_back(tn/tt[tsz-2]-1);
} else ve.push_back(tn/tt[tsz-2]);
}
if(tn%tt[tsz-2]==0) tn = tt[tsz-2];
else tn %= tt[tsz-2];
}
}
for(int ii=0; ii<ve.size(); ++ii) {
cout<<ve[ii];
}
for(int ii=i-ve.size()-1; ii>=0; --ii) {
cout<<ve[ii];
}
cout<<endl;
return;
}
int main() {
ull len = 3;
while(1) {
t[len] = 9*tt[len-2];
tt[len] = 10*tt[len-2];
ans += t[len];
if(ans>=M) break;
len++;
}
for(int i=3; i<=len; ++i) tans[i]+=t[i]+tans[i-1];
slove();
return 0;
}
E - Sinking Land
算法：BFS + 优先队列
题目大意
有一个小岛，其面积为 H 行乘以 W 列，即总的格子数为 H×W。小岛四周被海水包围。
小岛被划分为 H 行 W 列的正方形小块，每一块的海拔高度由二维数组 A[i][j] 给出，其中 i 是行号，j 是列号。
每年海平面上升 1 单位高度。根据以下规则，一些小块会逐渐沉入海中：
垂直或水平临海的小块，或者海拔高度不大于当前海平面高度的小块，将沉入海中。
当一个小块沉入海中时，与其垂直或水平相邻的、海拔高度不大于海平面的小块也会沉入海中。这个过程会连续发生，直到没有新的小块沉入海中。
任务是对每个年份 i（i=1,2,…,Y），求出经过 i 年后，岛上仍高于海平面的小块的总数。
算法思路
这题比较简单，其实就是海水蔓延的过程，通过BFS进行模拟即可，只不过需要通过priority_queue存储对应的数据即可。
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
using namespace std;
struct Node {
int x,y;
int ans;
bool operator<(const Node& b) const {
return ans>b.ans;
}
};
int h,w,yr;
int a[N];
int ta[1007][1007];
int tp[1007][1007];
priority_queue<Node> pq;
int ans;
void bfs(int nowyr) {
if(nowyr>yr) return;
while(!pq.empty() && nowyr>=pq.top().ans) {
--ans;
int x = pq.top().x;
int y = pq.top().y;
pq.pop();
for(int i=0; i<4; ++i) {
int tx = x + dx[i];
int ty = y + dy[i];
if(tx>=1 && tx<=h && ty>=1 && ty<=w && tp[tx][ty]==0) {
tp[tx][ty] = 1;
pq.push(Node {tx,ty,ta[tx][ty]});
}
}
}
a[nowyr] = ans;
bfs(nowyr+1);
}
void slove() {
cin>>h>>w>>yr;
for(int i=1; i<=h; ++i)
for(int j=1; j<=w; ++j)
cin>>ta[i][j];
ans = h * w;
for(int i=1; i<=h; ++i) {
if(w!=1) {
tp[i][1] = 1;
tp[i][w] = 1;
pq.push(Node {i,1,ta[i][1]});
pq.push(Node {i,w,ta[i][w]});
} else {
tp[i][1] = 1;
pq.push(Node {i,1,ta[i][1]});
}
}
for(int i=2; i<=w-1; ++i) {
if(h!=1) {
tp[1][i] = 1;
tp[h][i] = 1;
pq.push(Node {1,i,ta[1][i]});
pq.push(Node {h,i,ta[h][i]});
} else {
tp[1][i] = 1;
pq.push(Node {1,i,ta[1][i]});
}
}
bfs(1);
for(int i=1; i<=yr; ++i) cout<<a[i]<<endl;
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
slove();
return 0;
}