《牛客IOI周赛25-普及组》
分类:
IT文章
•
2023-11-08 17:09:18
A:水题
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e6 + 5;
const int M = 2000 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
LL x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
}
using namespace FASTIO;
int main() {
int n;n = read();
string s;cin >> s;
for(int i = 1;i <= n;++i) {
int x = s[i - 1] - 'a';
int len = i % 26;
if(i & 1) {
int ma = x + len;
if(ma >= 26) {
ma -= 26;
}
printf("%c",ma + 'a');
}
else {
int ma = x - len;
if(ma < 0) {
ma += 26;
}
printf("%c",ma + 'a');
}
}
//system("pause");
return 0;
}
View Code
B:
我们从后向前看,如果当前是x开头,那么后面的下一个x开头的答案都可以用当前x开头来替换。
所以我们每个位置都继承当前以x开头的答案有多少。
那么对于一段x ~ x的区间,我们只需要找到里面比x多的数的答案就是前一个x比后一个x可以多的。
一开始开了longlong爆内存了,int就够了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e6 + 5;
const int M = 2000 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
LL x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
}
using namespace FASTIO;
int sum[N][37];
int pos[40];
int cal(char c) {
if(c >= '0' && c <= '9') return c - '0';
else {
return c - 'A' + 10;
}
}
int main() {
string s;cin >> s;
int n = s.size();
for(int i = n;i >= 1;--i) {
int x = cal(s[i - 1]);
sum[i][36] = pos[x];
pos[x] = i;
}
int x = cal(s[n - 1]);
sum[n][x] = 1;
for(int i = n - 1;i >= 1;--i) {
for(int j = 0;j <= 35;++j) sum[i][j] = sum[i + 1][j];
int x = cal(s[i - 1]);
if(sum[i][36] == 0) sum[i][x]++;
for(int j = x + 1;j <= 35;++j) {
sum[i][x] += sum[i][j] - sum[sum[i][36]][j];
}
// for(int j = 0;j <= 35;++j) printf("sum[%d][%d] is %lld
",i,j,sum[i][j]);
}
LL ans = 0;
for(int i = 0;i <= 35;++i) ans += sum[1][i];
printf("%lld
",ans);
//system("pause");
return 0;
}
View Code
C:
其实这题我感觉不难。
我们按字母来存位置,dfs来找大于当前位置的下一个位置。
只需要记住可以替换的这一原则,那么我们每次找后面的最靠近我们的肯定是最优的。
而已串最长也就36,所以dfs的复杂度其实不高。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e6 + 5;
const int M = 2000 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
LL x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
}
using namespace FASTIO;
vector<int> vec[40];
int cal(char c) {
if(c >= '0' && c <= '9') return c - '0';
else {
return c - 'A' + 10;
}
}
string cha(int x) {
string t = "";
if(x >= 0 && x <= 9) t += (x + '0');
else t += ('A' + x - 10);
return t;
}
void dfs(int x,int pos,string s) {
cout << s << "
";
for(int i = x + 1;i <= 35;++i) {
if(vec[i].size() != 0) {
int pt = lower_bound(vec[i].begin(),vec[i].end(),pos) - vec[i].begin();
//printf("pos is %d i is %d pt is %d
",pos,i,pt);
if(pt >= vec[i].size()) continue;
dfs(i,vec[i][pt],s + cha(i));
}
}
}
int main() {
string s;cin >> s;
int n = s.size();
for(int i = 1;i <= n;++i) {
int x = cal(s[i - 1]);
vec[x].push_back(i);
}
for(int i = 0;i <= 35;++i) {
if(vec[i].size() != 0) {
int pos = vec[i][0];
dfs(i,pos,cha(i));
}
}
// system("pause");
return 0;
}
/*
AA0201B
*/
View Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e5 + 5;
const int M = 2000 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
LL x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
}
using namespace FASTIO;
int n,a[105][105],b[4][2] = {1,0,-1,0,0,1,0,-1};
int ans = INF,f = 0;
bool vis[105][105];
void dfs(int x,int y,int low,int up) {
if(f) return ;
if(x == n && y == n) {
f = 1;
return ;
}
for(int i = 0;i < 4;++i) {
int px = x + b[i][0];
int py = y + b[i][1];
if(px >= 1 && px <= n && py >= 1 && py <= n) {
if(!vis[px][py] && a[px][py] >= low && a[px][py] <= up) {
vis[px][py] = 1;
dfs(px,py,low,up);
}
}
}
}
int main() {
n = read();
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j) a[i][j] = read();
int L = 0,r = 3000;
while(L <= r) {
int mid = (L + r) >> 1;
f = 0;
for(int i = 0;i <= 3000;++i) {
int low = i,up = i + mid;
if(a[1][1] >= low && a[1][1] <= up) {
memset(vis,0,sizeof(vis));
vis[1][1] = 1;
dfs(1,1,low,up);
}
if(f) break;
}
if(f) ans = mid,r = mid - 1;
else L = mid + 1;
}
printf("%d
",ans);
//system("pause");
return 0;
}