A - Accept or Reject
题意：
长度为n的字符串中是否存在长度为m的回文子串
Solution：
马拉车裸题
Code：
#include<bits/stdc++.h>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 5e6 + 10;
int m, n;
bool Mannacher(string s){
string t = "$#";
for (int i = 0; i < s.size(); ++i){
t += s[i];
t += "#";
}
vector<int> p(t.size(), 0);
int mx = 0, id = 0;
for (int i = 1; i < t.size(); ++i){
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (t[i + p[i]] == t[i - p[i]])++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
}
for (int i = 1; i < t.size(); i++) {
if ((((p[i] - 1)%2) == (m%2))&&((p[i]-1)>=m)) return 1;
}
return 0;
}
int main() {
O_O;
string s;
cin >> n >> m;
cin >> s;
if (Mannacher(s)) cout << "Accept\n";
else cout << "Reject\n";
return 0;
}
/*
5 5
bbabacaba
//↑Mannacher中判断使用 p[i]-1==m 反例
*/Others:
- 虽是累积，旦并非每一种可能的回文串数字都会在p中出现
B - Beza's Hangover
Solution：
线段树单点修改，区间查询裸题
Code：
include<bits/stdc++.h>
#include<unordered_map>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
string s[maxn];
unordered_map<string, ll>sco;
ll tree[maxn << 2];
void build(int rt, int L, int R){
if (L == R){
tree[rt] = sco[s[L]];
return;
}
int mid = L + R >> 1;
build(rt << 1, L, mid);
build(rt << 1 | 1, mid + 1, R);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void update(int rt, int L, int R, int p, ll x){
if (L == R){
tree[rt] = x;
return;
}
int mid = L + R >> 1;
if (p <= mid) update(rt << 1, L, mid, p, x);
else update(rt << 1 | 1, mid + 1, R, p, x);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
ll query(int rt, int L, int R, int l, int r){
if (R<l || L>r) return 0;
if (R <= r && L >= l) return tree[rt];
int mid = L + R >> 1;
return query(rt << 1, L, mid, l, r) + query(rt << 1 | 1, mid + 1, R, l, r);
}
int main() {
O_O;
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 0; i < m; i++) {
string ss;
ll v;
cin >> ss >> v;
sco[ss] = v;
}
build(1, 1, n);
for (int i = 1; i <= q; i++) {
int u;
cin >> u;
if (u == 1) {
int x;
string y;
cin >> x >> y;
update(1, 1, n, x, sco[y]);
}
else {
ll l, r;
cin >> l >> r;
ll res=query(1, 1, n, l, r);
ll ans = ((ll)r - (ll)l + 1ll) * 60ll;
if (res * 2 > ans) cout << "YES\n";
else cout << "NO\n";
}
}
return 0;
}Others:
- 输入时数组与build中下标统一
C - Call from Mendes
Solution:
………等等等明天趴 哭啦QAQ
D - Drinking to turn red
Solution:
贪心
Code：
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
struct node {
double x, y;
double r;
double val;
}ed[maxn], s;
bool cmp(node a, node b) {
if (a.val < b.val) return 1;
return 0;
}
int main() {
O_O;
int n;
cin >> n >> s.x >> s.y;
for (int i = 1; i <= n; i++) {
cin >> ed[i].x >> ed[i].y >> ed[i].r;
ed[i].val = sqrt((ed[i].x - s.x) * (ed[i].x - s.x) + (ed[i].y - s.y) * (ed[i].y - s.y)) - ed[i].r;
}
sort(ed + 1, ed + 1 + n, cmp);
double r = 0.0, rr = 0.0;
for (int i = 1; i <= n; i++) {
if (rr >= ed[i].val) rr += ed[i].r;
else r += ed[i].val - rr, rr = ed[i].val + ed[i].r;
}
cout << fixed << setprecision(10) << r << "\n";
return 0;
}Others:
- 仍然不知道为什么用distance直接排序会导致精度错误（或许不是精度错误？//精度问题个鬼啊！就是wa啊！就是啊！ 不减半径排啥排（就是个憨憨
E - Everybody loves acai
Solution:
打表找规律 预处理 前2e6个数内只存在四个完全数
Code：
#include<bits/stdc++.h>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 5e6 + 10;
int main() {
O_O;
int n, m;
cin >> n;
while (n--) {
cin >> m;
if (m < 6) cout << "-1\n";
else if (m < 28) cout << "6\n";
else if (m < 496) cout << "28\n";
else if (m < 8128) cout << "496\n";
else cout << "8128\n";
}
return 0;
}F - Finally, christmas!
Solution：
扫描线+线段树裸题
Code：
#include<bits/stdc++.h>
#define ls nod<<1
#define rs (nod<<1)+1
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
int v[maxn];
struct L {
int x;
int y1, y2;
int state;
bool operator <(const L& ith) const {
return x < ith.x;
}
}line[maxn];
struct segment_tree {
int l, r;
int cover;
LL len;
}tree[maxn << 3];
void pushup(int nod) {
if (tree[nod].cover) tree[nod].len = (tree[nod].r - tree[nod].l);
else tree[nod].len = (tree[ls].len + tree[rs].len);
}
void build(int l, int r, int nod = 1) {
tree[nod].l = v[l];
tree[nod].r = v[r];
if (r - l <= 1)
return;
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid, r, rs);
}
void modify(int x, int y, int z, int nod = 1) {
int l = tree[nod].l, r = tree[nod].r;
if (x <= l && y >= r) {
tree[nod].cover += z;
pushup(nod);
return;
}
if (x < tree[ls].r)
modify(x, y, z, ls);
if (y > tree[rs].l)
modify(x, y, z, rs);
pushup(nod);
}
int main() {
int n;
int a, b=0, c, d;
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>a>>c>>d;
v[i] = b;
v[n + i] = d;
line[i] ={ a,b,d,1 };
line[i + n] ={ c,b,d,-1 };
}
sort(v + 1, v + 1 + (n << 1));
sort(line + 1, line + 1 + (n << 1));
build(1, n << 1);
unsigned long long ans = 0;
for (int i = 1; i <= 2 * n; i++) {
ans += tree[1].len * (line[i].x - line[i - 1].x);
modify(line[i].y1, line[i].y2, line[i].state);
}
cout << ans << endl;
return 0;
}G - Gorggeous Peter's Great Friend
Solution:
简单模拟
Code:
#include<bits/stdc++.h>
#include<unordered_map>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
string ss[maxn];
unordered_map<string, ll>mp,mmp;
ll score[maxn];
ll sss[maxn];
int main() {
int c, p, s;
string pro;
cin >> c >> p >> s;//候选人 问题数 提交数
for (int i = 1; i <= c; i++) cin >> ss[i],mmp[ss[i]]=0ll;
for (int i = 1; i <= p; i++) cin >> pro >> score[i], mp[pro] = i*1ll;
for (int i = 1; i <= s; i++) {
string na, po, ve;
cin >> na >> po >> ve;
if (ve == "AC")
if(mmp.find(na)!=mmp.end())
mmp[na] += score[mp[po]];
}
for (int i = 1; i <= c; i++) cout << ss[i] << " " << mmp[ss[i]] << "\n";
return 0;
}H - Hellcife is on fire
Solution:
dijkstra变形
Code:
#include<bits/stdc++.h>
#include<unordered_map>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
queue<int>q;
ll t[maxn];
struct Node {
int to, nxt;
ll val;
}edge[maxn << 1];
int cnt, hd[maxn << 1];
ll ans[maxn];
void add(int p, int q, ll o) { edge[cnt] = { q,hd[p],o }; hd[p] = cnt++; }
void init(){
cnt = 0;
memset(hd, -1, sizeof(hd));
for (int i = 0; i < maxn - 1; i++) ans[i] = 1e15;
}
void bfs() { //没T 你品 你细品
while (!q.empty()) {
int tmp = q.front(); q.pop();
for (int i = hd[tmp]; ~i; i = edge[i].nxt) {
if (ans[edge[i].to] > edge[i].val + ans[tmp] + t[edge[i].to]) {
ans[edge[i].to] = edge[i].val + ans[tmp] + t[edge[i].to];
q.push(edge[i].to);
}
}
}
}
int main() {
O_O;
int n, m, k;
cin >> n >> m >> k;
init();
for (int i = 1; i <= m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= n; i++) cin >> t[i];
for (int i = 1; i <= k; i++) {
int u;
cin >> u;
ans[u] = t[u];
q.push(u);
}
bfs();
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
return 0;
}I - Ivan and the swimming pool
Solution:
二分 + dfs
/（一开始全部方格都无效，按照权值大小从大到小依次加入，用并查集处理有效部分的联通块大小，维护
所有联通块大小的最大值，当最大值大于 时就找到了答案
Code：
#include<bits/stdc++.h>
#include<unordered_map>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
unordered_map<int, int>vis[maxn], de[maxn];
int s, n, m;
int ans,res;
int val[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
void dfs(int x, int y) {
res++;
vis[x][y] = 0;
for (int i = 0; i < 4; i++) {
int xx = x + val[i][0];
int yy = y + val[i][1];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && vis[xx][yy]) {
dfs(xx, yy);
}
}
}
bool check(int v) {
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (de[i][j] >= v) vis[i][j] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vis[i][j]) {
res = 0;
dfs(i, j);
cnt = max(cnt, res);
}
}
}
if (cnt >= s) return 1;
return 0;
}
int main() {
O_O;
cin >> s >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> de[i][j];
int l = 1, r = 1e9;
while (l <= r) {
int mid = l + r>>1;
if (check(mid)) l = mid+1,ans=mid;
else r = mid - 1;
}
cout << ans << "\n";
return 0;
}Others:
- dfs中把vis及时归零
- 二分的写法
（终于过了一次nice
J - Jingle Bells
Solution:
K - Kongey Donk
Solution：
简单dp转移方程式：dp[i][j]=max(dp[i-1][j+1],max(dp[i][j+1],dp[i+1][j+1]))+dp[i][j];
Code:
#include<bits/stdc++.h>
#define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int main() {
O_O;
int n, h;
ll maxx = 0;
cin>>n>>h;
ll tree[n + 10][h + 10]; //梦幻操作
for (int i = 0; i < n; i++) {
for (int j = 0; j < h; j++) {
cin>>tree[i][j];
maxx=max(maxx,tree[i][j]);
}
}
for (int i = h-2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (j == 0) tree[j][i] = max(tree[j][i + 1], tree[j + 1][i + 1])+tree[j][i];
else if (j == n - 1) tree[j][i] = max(tree[j][i + 1], tree[j - 1][i + 1])+tree[j][i];
else {
tree[j][i] = max(tree[j][i + 1], max(tree[j - 1][i + 1], tree[j + 1][i + 1]))+tree[j][i];
}
maxx = max(maxx, tree[j][i]);
}
}
cout << maxx << "\n";
return 0;
}Others:
- 边界处理
- 特殊情况例如只有一层，因此在输入时可先取max
京公网安备 11010502036488号