A - First Player
题目大意
顺时针给定一个序列, 序列的元素由一个字符串和一个数字组成; 我们需要从有最小数字的元素开始, 顺时针遍历整个序列, 并输出字符串;
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<string,int> PSI;
const int N=110;
int n;
vector<PSI> v;
signed main() {
cin >> n;
int pos = 0,minn = 1e9+10;
for (int i = 1; i <= n; i++) {
string a;
int b;
cin >> a >> b;
v.push_back({ a,b });
if (b < minn) {
minn = b;
pos = i-1;
}
}
for (int i = 1, j = pos; i <= n; j++, i++) {
if (j == n) j = 0;
cout << v[j].first << endl;
}
return 0;
}
B - Subscribers
题目大意
给定一个数, 只保留前三位数, 其他位数变为0; 若不足三位则直接输出原数;
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n;
signed main() {
string s;
cin >> s;
int len = s.size();
if (len < 4) cout << s;
else {
for (int i = 0; i < len; i++) {
if (i >= 3) cout << 0;
else cout << s[i];
}
}
return 0;
}
C - Virus
题目大意
给定一个只有'#'和'.'组成的矩阵, 问由'#'组成的X形状的各种大小的都有多少个
解题思路
数量不大, 直接暴力
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
char g[N][N];
int dx[] = { 1,1,-1,-1 }, dy[] = { 1,-1,1,-1 };
int n,m;
map<int, int> mp;
void check(int x, int y) {
bool f = true;
int idx = 0;
while (1) {
for (int i = 0; i < 4; i++) {
int a = x + dx[i]*(idx+1), b = y + dy[i]*(idx+1);
if (a<1 || a>n || b<1 || b>m||g[a][b] != '#') {
f = false;
break;
}
}
if (!f) break;
idx++;
}
mp[idx]++;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '#') {
check(i, j);
}
}
}
int num = min(n, m);
for (int i = 1; i <= num; i++) {
cout << mp[i] << ' ';
}
return 0;
}
D - A Piece of Cake
题目大意
给定一个长宽为n和m的矩形蛋糕, 蛋糕上有k个草莓; 然后我们要对着蛋糕竖着切a刀, 横着切b刀; 每一刀都给出其对应在x轴或y轴上的坐标; 注意切的时候不会切到有草莓的那一行或列; 并且也不会切边缘的行和列, 而草莓也不会在边缘的行和列上; 切完之后, 找到所有蛋糕块里面含有草莓数量最少和最多的数量, 并输出这两个数;
解题思路
这个题的长和宽数据比较大, 而且a和b也都是1e5级别的; 所以我们不能从矩阵或者每块蛋糕的角度出发; 而草莓数量也是1e5; 所有我们可以从每个草莓下手; 我们可以遍历所有草莓, 然后找到其所在的蛋糕块, 然后更新该蛋糕块上草莓的数量, 这个我们可以用map来完成; 对于怎么找对应的蛋糕块, 我们可以用二分查找小于草莓坐标的坐标最大的横竖两刀, 而这两刀的交点就是该蛋糕块的左上角, 我们可以用它来代表该蛋糕块; 如果map里的蛋糕块数量小于所有的蛋糕块数量((a+1) * (b+1)), 那说明有蛋糕块上没有草莓, 故最小值为0;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m,k;
map<PII, int> mp;
vector<PII> v;
set<int> s1;
set<int> s2;
signed main() {
cin >> m >> n >> k;
while (k--) {
int a, b;
cin >> a >> b;
v.push_back({ b,a });
}
sort(v.begin(), v.end());
int a, b;
cin >> a;
for (int i = 1; i <= a; i++) {
int x;
cin >> x;
s1.insert(x);
}
cin >> b;
for (int i = 1; i <= b; i++) {
int x;
cin >> x;
s2.insert(x);
}
for (int i = 0; i < v.size(); i++) {
int x = v[i].first;
int y = v[i].second;
int x1, y1;
auto p1 = s2.lower_bound(x);
if (p1 == s2.end()) x1 = 0;
else x1 = *p1;
auto p2 = s1.lower_bound(y);
if (p2 == s1.end()) y1 = 0;
else y1 = *p2;
mp[{x1, y1}]++;
}
int num = (a + 1) * (b + 1);
int res = 0;
int minn = 1e9 + 10;
int maxn = 0;
for (auto t : mp) {
int idx = t.second;
minn = min(minn, idx);
maxn = max(maxn, idx);
res += idx;
}
if (mp.size() <num) cout << 0 << ' ';
else cout << minn << ' ';
cout << maxn;
return 0;
}
E - Good Graph
题目大意
给定一个无向图, 有n个点和m条边并给出这m条边, 再给出k组{ xi, yi } ( i = 1, 2, 3...k), 如果所有的xi和yi之间都没有边相连, 那么这个无向图就是合法的; 现在再给出q组{ xj, yj } ( j = 1, 2, 3...q), 每一组就是一次询问, 问如果把当前的xj和yj相连, 那此时无向图是否合法;
注意可能存在重边或自环; 而且相连不一定是直接相连, 1-2-5这种情况也算1和5相连
解题思路
很明显的一个并查集问题, 初识情况就是给了许多个连通块; 然后给出k组限制, 一开始我还在想, k和q都是1e5级别的, 肯定不能去一个个查; 后来小莫提醒到了我, 不要去关注每个点, 只需要看每个连通块就行; 于是我们可以把k的限制看成是规定了某些连通块之间不能相连, 而不是点之间不能相连; 我们可以用set把不能相连的连通块存起来, 方便后期查找; 对于q组询问, 我们只需要看看给出的两个点所在的连通块是否在set里面存着, 如果没有则就是合法的;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int n,m,c,d;
int p[N];
set<PII> s;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
if (find(a) != find(b)) p[find(b)] = find(a);
}
cin >> c;
for (int i = 1; i <= c; i++) {
int a, b;
cin >> a >> b;
s.insert({ find(a),find(b)});
}
cin >> d;
for (int i = 1; i <= d; i++) {
int a, b;
cin >> a >> b;
if ((s.count({ find(a),find(b) })) || (s.count({ find(b),find(a) }))) {
cout << "No" << endl;
}
else cout << "Yes" << endl;
}
return 0;
}
F - Shift Table
题目大意
待定.....
解题思路
待定....
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int w[N],d[N];
int n,m,idx;
bool st[N];
vector<int> v[N];
int dijkstra(){
memset(d,0x3f,sizeof d);
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
d[1]=0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int x=t.second;
if(st[x]) continue;
st[x]=true;
for(int p:v[x]){
if(d[p]>d[x]+w[p]){
d[p]=d[x]+w[p];
heap.push({d[p],p});
}
}
}
if(d[m]==0x3f3f3f3f) return -1;
else return d[m]-1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int k;
cin>>k;
w[i+m] =1;
for(int j=1;j<=k;j++){
int x;
cin>>x;
v[x].push_back(i+m);
v[i+m].push_back(x);
}
}
cout<<dijkstra();
return 0;
}