B - Rotate
题目大意
给定一个n*n的矩阵, 要求把矩阵的最外围按照顺时针转动一个数据, 输出转动后的矩阵;
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int n, m;
char g[110][110];
bool f = false;
signed main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> g[i][j];
}
}
int x = g[1][1];
for (int i = 1; i < n; i++) g[i][1] = g[i + 1][1];
for (int i = 1; i < n; i++) g[n][i] = g[n][i+1];
for (int i = n; i > 1; i--) g[i][n] = g[i - 1][n];
for (int i = n; i > 1; i--) g[1][i] = g[1][i-1];
g[1][2] = x;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout<< g[i][j];
}
cout << endl;
}
return 0;
}
C - Medicine
题目大意
小莫有一个吃药列表, 每个药物有两个参数a, b; 表示从吃a天, 每天吃b个; 给定一个数量k, 问第一次吃药数量小于等于k的的第几天;
解题思路
算是一个比较明显的二分, 需要注意的一点是二分的上限要大于最大的天数, 否则当k=0的时候会输出0, 而正确答案应该是最大天数+1;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
int n, m;
int a[N], b[N];
bool f=false;
bool check(int u) {
int res=0;
for (int i = 1; i <= n; i++) {
if (a[i] >= u) res += b[i];
}
if (res <= m) return true;
else return false;
}
signed main(){
cin >> n >> m;
int maxn=0;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
maxn=max(maxn,a[i]);
}
int l = 1, r = maxn+10;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) {
r=mid;
f=true;
}
else l = mid + 1;
}
if(f) cout<<l;
else cout<<0;
return 0;
}
D - Add One Edge
题目大意
现在有n1+n2个节点和m条边, 这些节点被分到节点1和节点n1+n2的两个连通块中, 节点1的连通块有n1个节点, 节点n1+n2的连通块有n2个节点; 现在我们在两个连通块中各找一个节点, 在这两个节点之间连一条边; 问从节点1到节点n1+n2的最短路径(边的个数)的最大值为多少;
解题思路
该题的题面多少有点坑, 很容易把人的思考重心放到该怎么确定两边要连通的点, 但是思考过后才发现一个样; 我们只需要两边各进行一次最短路, 找到两个连通块中的点到各自中心点的距离, 然后找到两边各自距离中心点最远的点, 这两个距离相加后+1就是答案了;
神秘代码
#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
int n1,n2, m;
vector<int> v[N];
int d1[N], d2[N];
bool st[N];
int dijkstra(int u,int d[]) {
int res = 0;
d[u]=0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({ 0,u });
while (heap.size()) {
auto t = heap.top();
heap.pop();
int id = t.second;
res = max(res, d[id]);
if (st[id]) {
continue;
}
st[id] = true;
for (int j : v[id]) {
if (d[j] > d[id] + 1) {
d[j] = d[id] + 1;
heap.push({ d[j],j });
}
}
}
return res;
}
signed main() {
cin >> n1 >> n2 >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
memset(d1, 0x3f, sizeof d1);
memset(d2, 0x3f, sizeof d2);
int a=dijkstra(1,d1);
int b=dijkstra(n1 + n2,d2);
cout << a + b + 1;
return 0;
}
E - Family and Insurance
题目大意
首先给出2~n中每人的父亲是谁(1是辈分最大的), 组成一个家庭族谱; 该家族一共录有m份保险, 每份保险有两个参数a, b; a表示是给谁录的保险, b表示该保险同样可以作用于a往下的b代子孙; 问该家族中一共多少人有保险;
解题思路
保险个数和家族人数都是3e5, 所以我想着每遍历一个保险就去操作一遍家族成员就很费时间的; 所以我想着能不能在遍历保险的时候只打标记, 最后只遍历一次家族成员; 在尝试过后发现是可以的; 我们用一个数组作为标记st[a] = b, 表示成员a上有保险, 并且其子孙b代都可以享用; 打完标记后用bfs遍历家族成员, 遇到有保险的成员就可以把保险传递下去, st[c] = st[a] - 1; 这样就需要遍历一遍家庭成员就可以得到所有有保险的人员个数;
神秘代码
#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
int n, m, res;
int p[N];
vector<int> v[N];
int st[N];
void bfs() {
queue<int> q;
q.push(1);
while (q.size()) {
int t = q.front();
q.pop();
if (st[t]) res++;
for (int x : v[t]) {
if (st[t]) {
st[x] = max(st[x],st[t] - 1);
}
q.push(x);
}
}
}
signed main() {
cin >> n >> m;
for (int i = 2; i <= n; i++) {
cin >> p[i];
v[p[i]].push_back(i);
}
while (m--) {
int x, y;
cin >> x >> y;
st[x] = max(st[x], y+1);
}
bfs();
cout << res;
return 0;
}
F - Box in Box
题目大意
解题思路
神秘代码
标签:AtCoder,abc,309,int,res,long,st,节点,define
From: https://www.cnblogs.com/mostimali/p/17790080.html