A - Attack
题目大意
给定两个数a和b, 问我们需要进行多少次a-b, 才能让a小于等于0
解题思路
签到题不多嗦了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
signed main(){
int a,b,c;
cin>>a>>b;
if(a%b) c=a/b+1;
else c=a/b;
cout<<c;
return 0;
}
B - Find snuke
题目大意
给定一个字符矩阵以及它的长和宽, 问在这个矩阵中是否存在水平, 竖直或者对角线方向上存在一串连续的字符串"sunke" (注意是只能沿着这三个方向的其中一个,中途不能转向), 如果存在则输出五个字符的坐标
解题思路
我们可以在输入矩阵的时候把所有's'的位置都存到vector里面, 之后我们只需要遍历vector里的坐标即可; 由题意得字符串的方向一共有8种可能, 可以先遍历's'坐标的8个方向, 如果有'u', 那么我们就可以沿着那个方向遍历一遍即可
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
char s[N][N];
int dx[] = { 1,0,-1,0,1,1,-1,-1 }, dy[] = { 0,1,0,-1,-1,1,-1,1 };
char str[5] = { 's','n','u','k','e' };
vector<PII> v;
vector<PII> z;
int n, m;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
if (s[i][j] == 's') v.push_back({ i,j });
}
}
for (auto t : v) {
for (int i = 0; i < 8; i++) {
z.push_back({ t.first,t.second });
bool f = true;
for (int j = 1; j <=4; j++) {
int x = t.first + dx[i]*j;
int y = t.second + dy[i]*j;
if (x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] == str[j]) {
z.push_back({ x,y });
}
else {
f = false;
z.clear();
break;
}
}
if (f) {
for (auto p : z) {
cout << p.first << ' ' << p.second << endl;
}
return 0;
}
}
}
return 0;
}
C - Almost Equal
题目大意
给定n个只由小写字母组成的相同长度的字符串, 你可以改变各个字符串之间的顺序, 问是否存在一种排序使得, 每一个字符串都与它下一个的字符串只有一个字符不同;
注意: 两个字符串的某个字符相同意思是该字符在两个字符串的位置也相同; eg: abed和abcd是合法的,因为他们只有e和c不同, 而abcd和dcba是不合法的, 他们四个字符都不同;
解题思路
这个题吧...我一直想不到什么好的方法; 最后看数量都很小, 死马当活马医用next_permutation排序来暴力做了一下, 没想到直接过了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;
string s[10];
int n, m;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
sort(s + 1, s + 1 + n);
do {
bool f = true;
for (int i = 1; i < n; i++) {
int num = 0;
for (int j = 0; j < m; j++) {
if (s[i][j] != s[i + 1][j]) {
num++;
if (num == 2) {
f = false;
break;
}
}
}
if (!f) break;
}
if (f) {
cout << "Yes";
return 0;
}
} while (next_permutation(s + 1, s + 1 + n));
cout << "No";
return 0;
}
D - Impartial Gift
题目大意
小莫打算送给A和B一人一份礼物, 对于A和B, 小莫各有一份礼物价值名单a和b, 各自的礼物会从各自的礼物名单中选出; 现在有个要求是两人的礼物价值相差不能超过k; 问送给两人的礼物总价值最大为多少
解题思路
这个题的思路很简单, 无非就是先遍历名单a, 对于每个礼物的价值a[i], 我们要在b里面找出a[i]-k到a[i]+k这个区间里最大的数, 然后更新最大值即可; 这题难点主要在数据范围较大, 容易tle, 所以我们在查找时都用二分即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;
vector<int> a;
vector<int> b;
int n, m,k;
signed main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a.push_back(x);
}
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
b.push_back(x);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int maxn = -1;
for (int i = 0; i < n; i++) {
int l = a[i] - k;
int r = a[i] + k;
auto c = lower_bound(b.begin(), b.end(), l);
int res = c - b.begin();
if (c == b.end()||b[res]>r) continue;
auto d= upper_bound(b.begin(), b.end(), r);
int idx = d - b.begin()-1;
if (b[idx] < l) continue;
maxn = max(maxn, a[i] + b[idx]);
}
cout << maxn;
return 0;
}
E - Isolation
题目大意
题目给定了由1~n编号的n个顶点, 初始情况下没有边与他们相连; 接下来有k次操作, 每次操作有两种选择: 一是"1 u v" 表示建立一条边将顶点u和v相连; 二是"2 u" 表示删除所有与顶点u相连的边;
对于每一次操作结束后, 需要输出当前有多少个顶点是没有边与它们相连的
解题思路
题目问孤立点的个数, 但是我们更容易求出联通点的个数, 最后用总数减一下即可;
我们可以用一个setst[N]来储存每个点都有哪些点与其相连; 对于1操作直接插入即可, 对2操作我们可以用erase清楚其联通点与当前点的边, 再用clear处理当前点即可; 注意数量的变化, 什么时候+1或者-1;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int n,k,idx;
set<int> st[N];
signed main(){
cin>>n>>k;
int num=0;
for(int i=1;i<=k;i++){
int a;
cin>>a;
if(a==1){
int x,y;
cin>>x>>y;
if(st[x].size()==0) num++;
if(st[y].size()==0) num++;
st[x].insert(y);
st[y].insert(x);
}
else{
int x;
cin>>x;
if(st[x].size()!=0) num--;
for(int t:st[x]){
st[t].erase(st[t].find(x));
if(st[t].size()==0) num--;
}
st[x].clear();
}
cout<<n-num<<endl;
}
return 0;
}
F - Merge Set
题目大意
待定.....
解题思路
待定....
神秘代码
#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;
}