https://www.acwing.com/problem/content/discussion/content/5608/
讨论这道题我已经WA了10次死去活来了,大家帮忙挑个错吧。。。
本来是80分的代码,被我找出了错误,也就是有些人没有讨论对象这件事,于是我用了STLset进行优化,结果……
我***********真高兴……
代码大家查个错吧。。。
#include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
vector<int> v[N];
set<int> Set[N];
int n, cnt[N], ans[N];
bool cmp(int a, int b) {
if (cnt[a] == cnt[b]) return a < b;
return cnt[a] < cnt[b];
}
void work() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) v[i].clear(), ans[i] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &cnt[i]);
for (int j = 1; j <= cnt[i]; j++) {
int x; scanf("%d", &x);
v[x].push_back(i); //会第x题的人有i
Set[i].insert(x);
}
}
for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end(), cmp); //按照会的题目数量排序
for (int i = 1; i <= n; i++) {
for (int j = 1; j < v[i].size(); j++) {
//v[i][j - 1]和v[i][j]有同样会的题i
if (ans[v[i][j - 1]] == 0) ans[v[i][j - 1]] = v[i][j];
else if (ans[v[i][j - 1]] != v[i][j]) {
int res = ans[v[i][j - 1]];
if (cmp(v[i][j], res)) res = v[i][j];
printf("YES\n%d %d\n",v[i][j - 1], res);
return;
}
}
}
// for (int i = 1; i <= n; i++) printf("%d ", ans[i]); puts("");
for (int i = 1; i <= n; i++) { //对于每一个人,对他当前的“讨论对象”进行判断是否成立
if (!ans[i]) continue;
//如果ans[i]和i都有一道对方不会的题,那么这就是一组答案
int x = i, y = ans[i];
vector<int> abc; abc.clear();
set_intersection(Set[x].begin(), Set[x].end(), Set[y].begin(), Set[y].end(), inserter(abc, abc.begin()));
// printf("%d %d %d %d\n", x, y, Set[x].size(), Set[y].size());
// for (int i = 0; i < abc.size(); i++) cout << abc[i] << " "; puts("");
if (abc.size() < min(Set[x].size(), Set[y].size()))
{ printf("YES\n%d %d\n", x, y); return; }
}
puts("NO"); return;
}
int main() {
int t; scanf("%d", &t);
while (t--) work();
return 0;
}
那个每日一题打卡宣传我先不放上来了,因为目前缺了很多没有写……
先把可以匹配的括号匹配了,剩下的就是没法匹配的括号了。
对无法匹配的括号一样的括号进行修改操作即可
#include <bits/stdc++.h>
using namespace std;
string str;
stack<int> s;
int main() {
cin >> str;
int l = str.size(), ans = 0;
if (l & 1) { puts("0"); return 0; }
for (int i = 0; i < l; i++) {
if (s.empty()) s.push(i);
else if (str[s.top()] == '(' && str[i] == ')') s.pop(); //匹配
else s.push(i); //不匹配
}
if (s.size() >= 2) { //还未匹配完
int w = s.top(); s.pop();
if (str[w] == ')')
{for (int i = 0; i < w; i++) if (str[i] == ')') ans++;}
else
{for (int i = w; i < l; i++) if (str[i] == '(') ans++;}
}
printf("%d", ans);
return 0;
}
那个每日一题打卡宣传我先不放上来了,因为目前缺了很多没有写……
先把可以匹配的括号匹配了,剩下的就是没法匹配的括号了。
对无法匹配的括号一样的括号进行修改操作即可
#include <bits/stdc++.h>
using namespace std;
string str;
stack<int> s;
int main() {
cin >> str;
int l = str.size(), ans = 0;
if (l & 1) { puts("0"); return 0; }
for (int i = 0; i < l; i++) {
if (s.empty()) s.push(i);
else if (str[s.top()] == '(' && str[i] == ')') s.pop(); //匹配
else s.push(i); //不匹配
}
if (s.size() >= 2) { //还未匹配完
int w = s.top(); s.pop();
if (str[w] == ')')
{for (int i = 0; i < w; i++) if (str[i] == ')') ans++;}
else
{for (int i = w; i < l; i++) if (str[i] == '(') ans++;}
}
printf("%d", ans);
return 0;
}
就是晚了点
我$\Huge2020.12.12$开始学C艹,并且在别人的推荐下阅读了李煜东(@lydrainbowcat)大佬的巨著《算法竞赛进阶指南》,从中了解到了AcWing,于$\Huge2021.4.5$加入AcWing大家庭。
知道为什么吗?
后面有三个$7$,且前面的$8$和$6$平均数也是7。。。所以约等于中奖$5$个$7$!(狂逃)
改名要和我说!我还要更新的!
封禁家族的童鞋们都要祝我一周年快乐呀~(厚颜无耻)
$Q$:为什么我记得如此清楚来$AcWing$的日期?
$A$:因为我在注册当天报名了《算法竞赛进阶指南》打卡活动,根据记录的日期,我是在$2021/5/22$ $8:45:39$的时候报名的,所以在这之前我注册了这个号。但后来我找y总@yxc问了下实际注册日期发现差了好多(记错了。。。)所以我决定选择这么一个打卡活动一周年的日子发分享!根据y总的描述(逃)我的注册时间是……
$Q$:你不是早就说不上线要毕业考了吗?怎么还在。。。
$A$:万分尴尬后来发现没那么紧张。。。原本是以为毕业考时间和周年庆的时间撞车了,结果后来宣布六月中旬才考……AcWing的六年级同学,加油鸭!同时我换了个头像,等到毕业后换回来!这是我自己拍的一个头像,比原来的那个找PPT的好多了(如果你没看到那个全是文字的头像,别来找我要,太难看了。。。)
而且还换了个背景……
和我拼团匹配到的两位同学我会用两个小号关注!(记得提醒我)别问我是怎么知道是谁的……
目标一:A+B题解阅读量达到1w,点赞数达到150,收藏数达到100!(收藏是截屏后才达到的)
目标二:在一周年前让封禁家族成员数量达到50!
目标三:七个月前发的所有分享(我指的是第三面)阅读量全部超过100,且排序算法整理最多,破1000!排序算法整理2位列第二!
目标四:关注题解分享写得好的大佬!以及同学。。。
这个嘛。。。不发图片了
还未实现
不会有奖励的
逃
luogu
额