PTA | 团体天梯赛
L1-064 估值一亿的AI核心代码
分数 20 作者 陈越 单位 浙江大学
以上图片来自新浪微博。
本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：
- 无论用户说什么，首先把对方说的话在一行中原样打印出来；
- 消除原文中多余空格：把相邻单词间的多个空格换成 \(1\) 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；
- 把原文中所有大写英文字母变成小写，除了
I； - 把原文中所有独立的
can you、could you对应地换成I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词； - 把原文中所有独立的
I和 me 换成you； - 把原文中所有的问号
?换成惊叹号!； - 在一行中输出替换后的句子作为 AI 的回答。
输入格式：
输入首先在第一行给出不超过 \(10\) 的正整数 \(N\)，随后 \(N\) 行，每行给出一句不超过 \(1000\) 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。
输出格式：
按题面要求输出，每个 AI 的回答前要加上 AI:
和一个空格。
输入样例：
6
Hello ?
Good to chat with you
can you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know输出样例：
Hello ?
AI: hello!
Good to chat with you
AI: good to chat with you
can you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
现在编译错误。。。
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
while(getline(cin,str)){
int len=str.length();
cout<<str<<endl;
cout<<"AI: ";
while(str[0]==' '){
str.erase(0);
len--;
}
int cur=1;
while(cur<len){
if(str[cur]!=' '){
cur++;
}if(ispunct(str[cur])){
while(cur-1!=0 && str[cur-1]=='0'){
str.erase(cur-1);
cur--;
}
}else{
cur++;
while(cur<len && str[cur]==" "){
str.erase(cur);
len--;
}
}
}
while(str[len-1]==' '){
str.erase(len-1);
len--;
}
cur=0;
while(cur!=len){
if(isupper(str[cur]) && str[cur]!='I'){
str[cur]+=32;
}
cur++;
}
string a[2]={"I","me"};
for(int i=0;i<2;i++){
string::iterator name=find(str.begin(),str.end(),a[i]);
while(name!=str.end()){
str=string(str.begin(),name)+"you"+string(name+a[i].length(),str.end());
name=find(str.begin(),str.end(),a[i]);
}
}
string::iterator target=find(str.begin(),str.end(),"can you");
while(target!=str.end()){
str=string(str.begin(),target)+"I can"+string(target+7,str.end());
target=find(str.begin(),str.end(),"can you");
}
target=find(str.begin(),str.end(),"could you");
while(target!=str.end()){
str=string(str.begin(),target)+"I could"+string(target+9,str.end());
target=find(str.begin(),str.end(),"could you");
}
cur=0;
while(cur!=len){
if(str[cur]=='?'){
str[cur]='!';
cur++;
}
}
cout<<str<<endl;
}
return 0;
}Code2
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 5 | 答案正确 | ||
| 1 | 444 | 3 | 答案错误 | 0 / 3 | |
| 2 | 440 | 3 | 答案正确 | 1 / 1 | |
| 3 | 452 | 4 | 答案正确 | 3 / 3 | |
| 4 | 384 | 4 | 答案错误 | 0 / 2 | |
| 5 | 404 | 3 | 答案正确 | 1 / 1 |
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
getchar();
string str;
while(n--){
getline(cin,str);
int len=str.length();
cout<<str<<endl; //把对方说的话在一行中原样打印出来
//删除行首的空格
while(str[0]==' '){
str.erase(0,1);
len--;
}
//删除行内的空格
int cur=0;
while(cur<len){
if(str[cur]==' '){
cur++;
while(str[cur]==' ' && cur != len){
str.erase(cur,1);
len--;
}
}
cur++;
}
//删除标点符号前面的空格
for(int i=0;i<str.length();i++){
if(ispunct(str[i]) && str[i-1]==' '){
str.erase(i-1,1);
i--;
}
}
//删除行末的空格
while(str[len-1]==' '){
str.erase(len-1,1);
len--;
}
//变小写
cur=0;
while(cur!=len){
if(isupper(str[cur]) && str[cur]!='I'){
str[cur]+=32;
}
cur++;
}
//替换
string a[]={"I","me","can you","could you"};
string b[]={"you","you","I can","I could"};
for(int i=0;i<4;i++){
size_t target=str.find(a[i],0);
while(target!=string::npos){
bool flag=false;
if(target==0 && target+a[i].length()==str.length())
flag=true;
else if(target==0 && (str[target+a[i].length()]==' ' || ispunct(str[target+a[i].length()])))
flag=true;
else if((str[target-1]==' ' || ispunct(str[target-1])) && target+a[i].length()==str.length())
flag=true;
else if((str[target-1]==' ' || ispunct(str[target-1])) && (str[target+a[i].length()]==' ' || ispunct(str[target+a[i].length()])))
flag=true;
if(flag)
str=string(str.begin(),str.begin()+target)+b[i]+string(str.begin()+target+a[i].length(),str.end());
target=str.find(a[i],target+1);
}
}
for(auto i=str.begin();i!=str.end();i++){
if(*i=='?'){
*i='!';
}
}
cout<<"AI: "<<str<<endl;
}
return 0;
}Code3
230117 14
| 测试点 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|
| 0 | 452 | 5 | 答案正确 | 10 / 10 |
| 1 | 444 | 3 | 答案错误 | 0 / 3 |
| 2 | 440 | 3 | 答案正确 | 1 / 1 |
| 3 | 452 | 4 | 答案正确 | 3 / 3 |
| 4 | 384 | 4 | 答案错误 | 0 / 2 |
| 5 | 404 | 3 | 答案正确 | 1 / 1 |
这个方法比较好，避免了把 can you 替换后的 I
再次替换回去。但是依然不好解决独立字符串的定义。
#include <bits/stdc++.h>
using namespace std;
bool check_independence(string str,string target){
size_t p1=str.find(target);
size_t p2=p1+target.length();
if(p1==0 && p2==str.length())
return true;
if(p1==0 && p2<str.length())
if(!isalpha(str[p2]))
return true;
if(p1>0 && p2==str.length())
if(!isalpha(str[p1-1]))
return true;
if(p1>0 && p2<str.length())
if(!isalpha(str[p1-1]) && !isalpha(str[p2]))
return true;
return false;
}
int main(){
int n;
cin>>n;
getchar();
string str,word;
while(n--){
getline(cin,str);
int len=str.length();
// 把对方说的话在一行中原样打印出来
cout<<str<<endl<<"AI: ";
istringstream stream(str);
bool isfirst=true;
while(stream>>word){
// 变小写
for(char &c : word){
if(c!='I') c=tolower(c);
}
// 替换
if(word=="can" || word=="could"){
// if(word.find("can")!=string::npos || word.find("could")!=string::npos){
// if(word.find("can")!=string::npos) size_t p=word.find("can");
// else size_t p=word.find("could");
string next;
stream>>next;
if(next=="you"){
word="I "+word.substr();
}else{
word=word+" "+next;
}
}else if(word.find("I")!=string::npos || word.find("me")!=string::npos){
size_t p1,p2;
if(word.find("I")!=string::npos){
p1=word.find("I");
p2=p1+1;
}else{
p1=word.find("me");
p2=p1+2;
}
bool independence=true;
if(p1-1>=0 && isalpha(word[p1-1]))
independence=false;
if(p2<word.length() && isalpha(word[p2]))
independence=false;
if(independence)
word=word.substr(0,p1)+"you"+word.substr(p2);
}
// 判断前面要不要加空格
if(!isfirst && !ispunct(word[0])){
word=" "+word;
}
isfirst=false;
for(char &c:word){
if(c=='?') c='!';
}
cout<<word;
}
cout<<endl;
}
return 0;
}
Code From Liuchuo
有点太猛了，直接用正则表达式。我还不会。 #include <bits/stdc++.h>
using namespace std;
string s;
int main() {
getline(cin, s);
while (getline(cin, s)) {
cout << s << '\n' << "AI: ";
s = regex_replace(s, regex(R"(\s+)"), " ");
s = regex_replace(s, regex(R"(^\s+|\s+$|\s+(?=\W))"), "");
s = regex_replace(s, regex(R"(\bI\b)"), "mark_mark");
for (int i = 0; i < (int)s.size(); i++) if (s[i] != 'I') s[i] = tolower(s[i]);
s = regex_replace(s, regex(R"(\bcan you\b)"), "I can");
s = regex_replace(s, regex(R"(\bcould you\b)"), "I could");
s = regex_replace(s, regex(R"(mark_mark|\bme\b)"), "you");
s = regex_replace(s, regex(R"(\?)"), "!");
cout << s << '\n';
}
return 0;
}
Code4
230117 14
把ispunct()改成了!isalnum()还是A不了剩下的两个点。
| 测试点 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|
| 0 | 316 | 3 | 答案正确 | 10 / 10 |
| 1 | 444 | 3 | 答案错误 | 0 / 3 |
| 2 | 328 | 3 | 答案正确 | 1 / 1 |
| 3 | 456 | 4 | 答案正确 | 3 / 3 |
| 4 | 452 | 4 | 答案错误 | 0 / 2 |
| 5 | 452 | 3 | 答案正确 | 1 / 1 |
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
getchar();
string str;
while(n--){
getline(cin,str);
int len=str.length();
cout<<str<<endl; //把对方说的话在一行中原样打印出来
//删除行首的空格
while(str[0]==' '){
str.erase(0,1);
len--;
}
//删除行内的空格
int cur=0;
while(cur<len){
if(str[cur]==' '){
cur++;
while(str[cur]==' ' && cur != len){
str.erase(cur,1);
len--;
}
}
cur++;
}
//删除标点符号前面的空格
for(int i=0;i<str.length();i++){
if(ispunct(str[i]) && str[i-1]==' '){
str.erase(i-1,1);
i--;
}
}
//删除行末的空格
while(str[len-1]==' '){
str.erase(len-1,1);
len--;
}
//变小写，变标点，改用C++特性
for(auto &c:str){
if(isupper(c) && c!='I')
c=tolower(c);
if(c=='?')
c='!';
}
//替换
string a[]={"I","me","can you","could you"};
string b[]={"you","you","I can","I could"};
for(int i=0;i<4;i++){
size_t target=str.find(a[i],0);
while(target!=string::npos){
bool flag=false;
if(target==0 && target+a[i].length()==str.length())
flag=true;
else if(target==0 && (str[target+a[i].length()]==' ' || !isalnum(str[target+a[i].length()])))
flag=true;
else if((str[target-1]==' ' || !isalnum(str[target-1])) && target+a[i].length()==str.length())
flag=true;
else if((str[target-1]==' ' || !isalnum(str[target-1])) && (str[target+a[i].length()]==' ' || !isalnum(str[target+a[i].length()])))
flag=true;
if(flag)
str=string(str.begin(),str.begin()+target)+b[i]+string(str.begin()+target+a[i].length(),str.end());
target=str.find(a[i],target+1);
}
}
cout<<"AI: "<<str<<endl;
}
return 0;
}Code5
230117 14
AC代码
先把 can you 替换为 $ can，最后在替换
$ 符号为
I。这个方法也太刁钻了。
猜测：我先替换I或者me会导致新出现的you与can或could组队，导致错误。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
getchar();
string str;
while(n--){
getline(cin,str);
int len=str.length();
cout<<str<<endl; //把对方说的话在一行中原样打印出来
//删除行首的空格
while(str[0]==' '){
str.erase(0,1);
len--;
}
//删除行内的空格
int cur=0;
while(cur<len){
if(str[cur]==' '){
cur++;
while(str[cur]==' ' && cur != len){
str.erase(cur,1);
len--;
}
}
cur++;
}
//删除标点符号前面的空格
for(int i=0;i<str.length();i++){
if(ispunct(str[i]) && str[i-1]==' '){
str.erase(i-1,1);
i--;
}
}
//删除行末的空格
while(str[len-1]==' '){
str.erase(len-1,1);
len--;
}
//变小写，变标点，改用C++特性
for(auto &c:str){
if(isupper(c) && c!='I')
c=tolower(c);
if(c=='?')
c='!';
}
//替换
string a[]={"can you","could you","I","me"};
string b[]={"$ can","$ could","you","you"};
for(int i=0;i<4;i++){
size_t target=str.find(a[i],0);
while(target!=string::npos){
bool flag=false;
if(target==0 && target+a[i].length()==str.length())
flag=true;
else if(target==0 && (str[target+a[i].length()]==' ' || !isalnum(str[target+a[i].length()])))
flag=true;
else if((str[target-1]==' ' || !isalnum(str[target-1])) && target+a[i].length()==str.length())
flag=true;
else if((str[target-1]==' ' || !isalnum(str[target-1])) && (str[target+a[i].length()]==' ' || !isalnum(str[target+a[i].length()])))
flag=true;
if(flag)
str=string(str.begin(),str.begin()+target)+b[i]+string(str.begin()+target+a[i].length(),str.end());
target=str.find(a[i],target+1);
}
}
for(auto &c:str){
if(c=='$')
c='I';
}
cout<<"AI: "<<str<<endl;
}
return 0;
}L2-004 这是二叉搜索树吗？
分数 25 作者 陈越 单位 浙江大学
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
- 其左子树中所有结点的键值小于该结点的键值；
- 其右子树中所有结点的键值大于等于该结点的键值；
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数 \(N（≤1000）\)。随后一行给出 \(N\) 个整数键值，其间以空格分隔。
输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出
YES ，然后在下一行输出该树后序遍历的结果。数字间有 \(1\)
个空格，一行的首尾不得有多余空格。若答案是否，则输出
NO。
输入样例 1：
7
8 6 5 7 10 8 11输出样例 1：
YES
5 7 6 8 11 10 8输入样例 2：
7
8 10 11 8 6 7 5输出样例 2：
YES
11 8 10 7 5 6 8输入样例 3：
7
8 6 8 5 10 9 11输出样例 3：
NO代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 6 / 6 | |
| 1 | 440 | 4 | 答案错误 | 0 / 6 | |
| 2 | 316 | 3 | 答案正确 | 2 / 2 | |
| 3 | 476 | 3 | 运行时错误 | 0 / 3 | |
| 4 | 452 | 3 | 答案错误 | 0 / 3 | |
| 5 | 4544 | 10 | 答案正确 | 2 / 2 | |
| 6 | 444 | 3 | 答案正确 | 2 / 2 | |
| 7 | 324 | 3 | 答案正确 | 1 / 1 |
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* l;
Node* r;
};
bool judge(vector<int> v){
if(v.size()<=1){
return true;
}
int l_begin,l_end,r_begin,r_end;
int head=v[0];
l_begin=1;
l_end=1;
while(v[l_end]<head){
l_end++;
}
for(size_t i=l_end;i<v.size();i++){
if(v[i]<head){
return false;
}
}
r_begin=l_end;
r_end=v.size();
vector<int> l_sub(v.begin()+l_begin,v.begin()+l_end);
vector<int> r_sub(v.begin()+r_begin,v.begin()+r_end);
return judge(l_sub) && judge(r_sub);
}
Node* create_tree(vector<int> v){
if(v.size()==0){
return NULL;
}
int l_begin,l_end,r_begin,r_end;
int head=v[0];
l_begin=1;
l_end=1;
while(v[l_end]<head && l_end<v.size()){
l_end++;
}
r_begin=l_end;
r_end=v.size();
vector<int> l_sub(v.begin()+l_begin,v.begin()+l_end);
vector<int> r_sub(v.begin()+r_begin,v.begin()+r_end);
Node* node=new Node;
node->data=head;
node->l=create_tree(l_sub);
node->r=create_tree(r_sub);
return node;
}
bool first=true;
void space(){
if(!first){
cout<<" ";
}
first=false;
return;
}
void postPrint(Node* node){
if(node->l==NULL && node->r==NULL){
space();
cout<<node->data;
}else if(node->l==NULL){
postPrint(node->r);
space();
cout<<node->data;
}else if(node->r==NULL){
postPrint(node->l);
space();
cout<<node->data;
}else{
postPrint(node->l);
postPrint(node->r);
space();
cout<<node->data;
}
delete node;
}
int main(){
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
if(judge(v)){
cout<<"YES"<<endl;
Node* tree=create_tree(v);
postPrint(tree);
cout<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}Code2
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 476 | 4 | 答案正确 | 6 / 6 | |
| 1 | 436 | 4 | 答案正确 | 6 / 6 | |
| 2 | 460 | 3 | 答案正确 | 2 / 2 | |
| 3 | 384 | 4 | 答案正确 | 3 / 3 | |
| 4 | 416 | 4 | 答案正确 | 3 / 3 | |
| 5 | 4532 | 10 | 答案正确 | 2 / 2 | |
| 6 | 396 | 3 | 答案正确 | 2 / 2 | |
| 7 | 440 | 4 | 答案正确 | 1 / 1 |
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* l;
Node* r;
};
bool judge_1(vector<int> v){
if(v.size()<=1){
return true;
}
int l_begin,l_end,r_begin,r_end;
int head=v[0];
l_begin=1;
l_end=1;
while(v[l_end]<head && l_end<v.size()){
l_end++;
}
r_begin=l_end;
for(r_end=r_begin;r_end<v.size();r_end++){
if(v[r_end]<head){
return false;
}
}
vector<int> l_sub(v.begin()+l_begin,v.begin()+l_end);
vector<int> r_sub(v.begin()+r_begin,v.begin()+r_end);
return judge_1(l_sub) && judge_1(r_sub);
}
bool judge_2(vector<int> v){
if(v.size()<=1){
return true;
}
int l_begin,l_end,r_begin,r_end;
int head=v[0];
l_begin=1;
l_end=1;
while(v[l_end]>=head && l_end<v.size()){
l_end++;
}
for(r_begin=l_end,r_end=v.size();r_begin<r_end;r_begin++){
if(v[r_begin]>=head){
return false;
}
}
vector<int> l_sub(v.begin()+l_begin,v.begin()+l_end);
vector<int> r_sub(v.begin()+r_begin,v.begin()+r_end);
return judge_2(l_sub) && judge_2(r_sub);
}
Node* create_tree_1(vector<int> v){
if(v.size()==0){
return NULL;
}
int l_begin,l_end,r_begin,r_end;
int head=v[0];
l_begin=1;
l_end=1;
while(v[l_end]<head && l_end<v.size()){
l_end++;
}
r_begin=l_end;
r_end=v.size();
vector<int> l_sub(v.begin()+l_begin,v.begin()+l_end);
vector<int> r_sub(v.begin()+r_begin,v.begin()+r_end);
Node* node=new Node;
node->data=head;
node->l=create_tree_1(l_sub);
node->r=create_tree_1(r_sub);
return node;
}
Node* create_tree_2(vector<int> v){
if(v.size()==0){
return NULL;
}
int l_begin,l_end,r_begin,r_end;
int head=v[0];
l_begin=1;
l_end=1;
while(v[l_end]>=head && l_end<v.size()){
l_end++;
}
r_begin=l_end;
r_end=v.size();
vector<int> l_sub(v.begin()+l_begin,v.begin()+l_end);
vector<int> r_sub(v.begin()+r_begin,v.begin()+r_end);
Node* node=new Node;
node->data=head;
node->l=create_tree_2(l_sub);
node->r=create_tree_2(r_sub);
return node;
}
bool first=true;
void space(){
if(!first){
cout<<" ";
}
first=false;
return;
}
void postPrint_1(Node* node){
if(node->l==NULL && node->r==NULL){
space();
cout<<node->data;
}else if(node->l==NULL){
postPrint_1(node->r);
space();
cout<<node->data;
}else if(node->r==NULL){
postPrint_1(node->l);
space();
cout<<node->data;
}else{
postPrint_1(node->l);
postPrint_1(node->r);
space();
cout<<node->data;
}
delete node;
}
void postPrint_2(Node* node){
if(node->l==NULL && node->r==NULL){
space();
cout<<node->data;
}else if(node->l==NULL){
postPrint_1(node->r);
space();
cout<<node->data;
}else if(node->r==NULL){
postPrint_1(node->l);
space();
cout<<node->data;
}else{
postPrint_1(node->l);
postPrint_1(node->r);
space();
cout<<node->data;
}
delete node;
}
int main(){
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
if(judge_1(v)){
cout<<"YES"<<endl;
Node* tree=create_tree_1(v);
postPrint_1(tree);
cout<<endl;
}else if(judge_2(v)){
cout<<"YES"<<endl;
Node* tree=create_tree_2(v);
postPrint_2(tree);
cout<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}L2-005 集合相似度
分数 25 作者 陈越 单位 浙江大学
给定两个整数集合，它们的相似度定义为：\(N_c \times N_t \times 100%\)。其中 \(N_c\) 是两个集合都有的不相等整数的个数，\(N_t\) 是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式：
输入第一行给出一个正整数\(N（≤50）\)，是集合的个数。随后\(N\)行，每行对应一个集合。每个集合首先给出一个正整数 \(M(\leq 10^4)\) ，是集合中元素的个数；然后跟\(M\)个 \([0,10^9]\) 区间内的整数。
之后一行给出一个正整数\(K（≤2000）\)，随后\(K\)行，每行对应一对需要计算相似度的集合的编号（集合从\(1\)到\(N\)编号）。数字间以空格分隔。
输出格式：
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后\(2\)位的百分比数字。
输入样例：
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3输出样例：
50.00%
33.33%代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 3 | 答案正确 | 12 / 12 | |
| 1 | 384 | 3 | 答案正确 | 3 / 3 | |
| 2 | 484 | 3 | 答案正确 | 3 / 3 | |
| 3 | 576 | 55 | 答案正确 | 3 / 3 | |
| 4 | 696 | 400 | 运行超时 | 0 / 4 |
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
double samilarity(vector<int> &a,vector<int> &b);
int main(){
int n;
cin>>n;
vector<vector<int>> v(n);
// 输入集合
for(int i=0;i<n;i++){
int t,temp;
cin>>t;
for(int j=0;j<t;j++){
cin>>temp;
v[i].push_back(temp);
}
}
int c;
cin>>c;
while(c--){
int a,b;
cin>>a>>b;
printf("%.2lf%\n",samilarity(v[a-1],v[b-1]));
}
return 0;
}
double samilarity(vector<int> &a,vector<int> &b){
int nc=0,nt=0;
unordered_map<int,int> mapa,mapb;
unordered_map<int,int> map;
for(auto &i:a){
mapa[i]=1;
}
for(auto &i:b){
mapb[i]=1;
}
for(auto &i:mapa){
if(map.count(i.first)==0){
map[i.first]=1;
}else{
map[i.first]++;
}
}
for(auto &i:mapb){
if(map.count(i.first)==0){
map[i.first]=1;
}else{
map[i.first]++;
}
}
for(auto i=map.begin();i!=map.end();i++){
// cout<<i->first<<" "<<i->second<<endl;
if(i->second>1){
nc++;
}
nt++;
}
return 100.0*nc/nt;
}Code2
测试得知 unordered_map 会比 map 多
40ms （测试点3）
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 12 / 12 | |
| 1 | 444 | 3 | 答案正确 | 3 / 3 | |
| 2 | 316 | 3 | 答案正确 | 3 / 3 | |
| 3 | 576 | 23 | 答案正确 | 3 / 3 | |
| 4 | 732 | 400 | 运行超时 | 0 / 4 |
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int nc,nt;
void samilarity(vector<int> &a,vector<int> &b){
nc=0,nt=0;
map<int,int> map;
for(auto i=a.begin();i!=a.end();i++){
map[*i]=-1;
}
for(auto i=b.begin();i!=b.end();i++){
if(map.find(*i)!=map.end()){
if(map[*i]==-1)
map[*i]=0;
}else{
map[*i]=1;
}
}
for(auto i=map.begin();i!=map.end();i++){
// cout<<i->first<<" "<<i->second<<endl;
if(i->second==0){
nc++;
}
nt++;
}
}
int main(){
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n,t,temp,a,b,c;
cin>>n;
vector<vector<int>> v(n);
for(int i=0;i<n;i++){
cin>>t;
while(t--){
cin>>temp;
v[i].push_back(temp);
}
}
cin>>c;
while(c--){
cin>>a>>b;
samilarity(v[a-1],v[b-1]);
printf("%.2lf%%\n",100.0*nc/nt);
}
return 0;
}即便改写了用定数组也超时 #include<iostream>
#include<vector>
using namespace std;
int nc,nt;
void samilarity(int a[],int b[],int lena,int lenb){
nc=0,nt=0;
int map[1000000];
memset(map,-1,sizeof(map));
for(int i=0;i<lena;i++){
map[a[i]]=1;
}
for(int i=0;i<lenb;i++){
if(map[a[i]]==1){
map[a[i]]=0;
}else{
map[b[i]]=2;
}
}
for(int i=0;i<1000000;i++){
if(map[i]==0){
nc++;
}
nt++;
}
}
int main(){
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n,t,temp,a,b,c;
cin>>n;
int set[50][10000];
int len[50];
for(int i=0;i<n;i++){
cin>>len[i];
for(int j=0;j<len[i];j++){
cin>>set[i][j];
}
}
cin>>c;
while(c--){
cin>>a>>b;
samilarity(set[a-1],set[b-1],len[a-1],len[b-1]);
printf("%.2lf%%\n",100.0*nc/nt);
}
return 0;
}
Code3
根据liuchuo代码的提示，使用了set，就能AC了
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 440 | 3 | 答案正确 | 12 / 12 | |
| 1 | 436 | 4 | 答案正确 | 3 / 3 | |
| 2 | 460 | 4 | 答案正确 | 3 / 3 | |
| 3 | 460 | 7 | 答案正确 | 3 / 3 | |
| 4 | 2860 | 110 | 答案正确 | 4 / 4 |
#include<iostream>
#include<vector>
#include<set>
using namespace std;
double samilarity(set<int> &a,set<int> &b){
int nc=0,nt=b.size();
for(auto i=a.begin();i!=a.end();i++){
if(b.find(*i)!=b.end()){
nc++;
}else{
nt++;
}
}
return 100.0*nc/nt;
}
int main(){
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n,t,temp,a,b,c;
cin>>n;
vector<set<int>> v(n);
for(int i=0;i<n;i++){
cin>>t;
while(t--){
cin>>temp;
v[i].insert(temp);
}
}
cin>>c;
while(c--){
cin>>a>>b;
printf("%.2lf%%\n",samilarity(v[a-1],v[b-1]));
}
return 0;
}L2-007 家庭房产
分数 25 作者 陈越 单位 浙江大学
给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式：
输入第一行给出一个正整数\(N（≤1000）\)，随后 \(N\) 行，每行按下列格式给出一个人的房产：
编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积 其中编号是每个人独有的一个\(4\)位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示\(-1\)）；\(k（0≤k≤5）\)是该人的子女的个数；孩子\(i\)是其子女的编号。
输出格式：
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
输入样例：
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100输出样例：
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
240120
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 436 | 3 | 答案正确 | 15 / 15 | |
| 1 | 440 | 3 | 答案正确 | 2 / 2 | |
| 2 | 492 | 3 | 答案正确 | 2 / 2 | |
| 3 | 572 | 7 | 答案正确 | 3 / 3 | |
| 4 | 812 | 38 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
struct fam{
set<int> member;
int house;
int area;
int size;
int first_id;
double house_pre;
double area_pre;
};
vector<fam> family;
void func(set<int> &member,int house,int area){
queue<int> merge_q;
stack<int> merge_s;
for(int i=0;i<family.size();i++){
for(auto &k:member){
if(family[i].member.find(k)!=family[i].member.end()){
merge_q.push(i);
merge_s.push(i);
break;
}
}
}
family.push_back(fam{member,house,area});
if(merge_q.size()>0){
int to=family.size()-1;
while(!merge_q.empty()){
int from=merge_q.front();
merge_q.pop();
for(auto &j:family[from].member){
family[to].member.insert(j);
}
family[to].house+=family[from].house;
family[to].area+=family[from].area;
}
while(!merge_s.empty()){
family.erase(family.begin()+merge_s.top());
merge_s.pop();
}
}
}
bool cmp(fam& a,fam& b){
if(abs(a.area_pre-b.area_pre)<1e-6)
return a.first_id<b.first_id;
return a.area_pre>b.area_pre;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int temp;
set<int> member;
int k,house,area;
for(int i=0;i<3;i++){
cin>>temp;
if(temp!=-1){
member.insert(temp);
}
}
cin>>k;
for(int i=0;i<k;i++){
cin>>temp;
member.insert(temp);
}
cin>>house>>area;
func(member,house,area);
}
for(auto &i:family){
i.size=i.member.size();
i.house_pre=(double)i.house/i.size;
i.area_pre=(double)i.area/i.size;
i.first_id=*(i.member.begin());
}
sort(family.begin(),family.end(),cmp);
cout<<family.size()<<endl;
for(auto &i:family){
printf("%04d %d %.3lf %.3lf\n",i.first_id,i.size,i.house_pre,i.area_pre);
}
return 0;
}L2-008 最长对称子串
分数 25 作者 陈越 单位 浙江大学
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出\(11\)。
输入格式：
输入在一行中给出长度不超过\(1000\)的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?输出样例：
11代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB
Code
240119
有一个疑问：为什么把++p改为p++就不能AC了，为什么？
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
getline(cin,str);
int len=str.length();
int max=(len>0)?1:0;
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
if(str[i]==str[j]){
int p=i,q=j;
while(p<q && str[++p]==str[--q]);
if(p>=q && j-i+1>max){
max=j-i+1;
}
}
}
}
cout<<max<<endl;
return 0;
}L2-009 抢红包
分数 25 作者 陈越 单位 浙江大学
没有人没抢过红包吧…… 这里给出\(N\)个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。
输入格式：
输入第一行给出一个正整数\(N（≤10^4）\)，即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：
\[ K , N_1 , P_1 , \cdots , N_K , P_K \]
其中\(K（0≤K≤20）\)是发出去的红包个数，\(N_i\) 是抢到红包的人的编号，\(P_i（>0）\)是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢\(1\)次，不能重复抢。
输出格式：
按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后\(2\)位）。每个人的信息占一行，两数字间有\(1\)个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。
输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB
Code
240119
#include<bits/stdc++.h>
using namespace std;
struct people{
int id;
int num;
int amount;
};
bool cmp(people& a,people& b){
if(a.amount==b.amount){
if(a.num==b.num)
return a.id<b.id;
return a.num>b.num;
}
return a.amount>b.amount;
}
int main(){
int n;
cin>>n;
vector<people> v(n);
for(int i=0;i<n;i++){
v[i].id=i+1;
v[i].num=0;
v[i].amount=0;
}
int k,person,money;
for(int i=0;i<n;i++){
cin>>k;
while(k--){
cin>>person>>money;
v[person-1].amount+=money;
v[i].amount-=money;
v[i].num++;
}
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<n;i++){
printf("%d %.2lf\n",v[i].id,v[i].amount/100.0);
}
return 0;
}L2-010 排座位
分数 25 作者 陈越 单位 浙江大学
布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。
输入格式：
输入第一行给出\(3\)个正整数：\(N（≤100）\)，即前来参宴的宾客总人数，则这些人从\(1\)到\(N\)编号；\(M\)为已知两两宾客之间的关系数；\(K\)为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客\(1\) 宾客\(2\) 关系，其中关系为\(1\)表示是朋友，\(-1\)表示是死对头。注意两个人不可能既是朋友又是敌人。最后\(K\)行，每行给出一对需要查询的宾客编号。
这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。
输出格式：
对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。
输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2输出样例：
No problem
OK
OK but...
No way代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB
Code1
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 432 | 3 | 答案正确 | 18 / 18 | |
| 1 | 436 | 13 | 答案错误 | 0 / 3 | |
| 2 | 456 | 10 | 答案正确 | 3 / 3 | |
| 3 | 324 | 3 | 答案正确 | 1 / 1 |
#include<bits/stdc++.h>
using namespace std;
void init(vector<int>& v){
for(int i=0;i<v.size();i++){
v[i]=i;
}
}
size_t findfa(vector<int>& v,int a){
if(v[a]==a){
return a;
}else{
v[a]=findfa(v,v[a]);
return v[a];
}
}
void merge(vector<int>& v,int a,int b){
if(findfa(v,a)!=findfa(v,b)){
v[findfa(v,b)]=v[findfa(v,a)];
}
}
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<int> fri(n);
vector<int> enemy(n);
// init
init(fri);
init(enemy);
int a,b,op;
for(int i=0;i<m;i++){
cin>>a>>b>>op;
a--;
b--;
if(op==1){
merge(fri,a,b);
}else if(op==-1){
merge(enemy,a,b);
}
}
for(int i=0;i<k;i++){
cin>>a>>b;
a--;
b--;
if(findfa(fri,a)==findfa(fri,b) && findfa(enemy,a)!=findfa(enemy,b))
cout<<"No problem"<<endl;
if(findfa(fri,a)!=findfa(fri,b) && findfa(enemy,a)!=findfa(enemy,b))
cout<<"OK"<<endl;
if(findfa(fri,a)==findfa(fri,b) && findfa(enemy,a)==findfa(enemy,b))
cout<<"OK but..."<<endl;
if(findfa(fri,a)!=findfa(fri,b) && findfa(enemy,a)==findfa(enemy,b))
cout<<"No way"<<endl;
}
return 0;
}Code2
240120
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 436 | 3 | 答案正确 | 18 / 18 | |
| 1 | 584 | 32 | 答案正确 | 3 / 3 | |
| 2 | 464 | 11 | 答案正确 | 3 / 3 | |
| 3 | 436 | 3 | 答案正确 | 1 / 1 |
#include<bits/stdc++.h>
using namespace std;
void init(vector<int>& v){
for(int i=0;i<v.size();i++){
v[i]=i;
}
}
size_t findfa(vector<int>& v,int a){
if(v[a]==a){
return a;
}else{
v[a]=findfa(v,v[a]);
return v[a];
}
}
void merge(vector<int>& v,int a,int b){
if(findfa(v,a)!=findfa(v,b)){
v[findfa(v,b)]=v[findfa(v,a)];
}
}
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<int> fri(n);
vector<pair<int,int>> enemy;
// init
init(fri);
int a,b,op;
for(int i=0;i<m;i++){
cin>>a>>b>>op;
if(a>=b){
swap(a,b);
}
a--;
b--;
if(op==1){
merge(fri,a,b);
}else if(op==-1){
enemy.push_back(make_pair(a,b));
}
}
for(int i=0;i<k;i++){
cin>>a>>b;
if(a>=b){
swap(a,b);
}
a--;
b--;
if(findfa(fri,a)==findfa(fri,b) && find(enemy.begin(),enemy.end(),make_pair(a,b))==enemy.end())
cout<<"No problem"<<endl;
if(findfa(fri,a)!=findfa(fri,b) && find(enemy.begin(),enemy.end(),make_pair(a,b))==enemy.end())
cout<<"OK"<<endl;
if(findfa(fri,a)==findfa(fri,b) && find(enemy.begin(),enemy.end(),make_pair(a,b))!=enemy.end())
cout<<"OK but..."<<endl;
if(findfa(fri,a)!=findfa(fri,b) && find(enemy.begin(),enemy.end(),make_pair(a,b))!=enemy.end())
cout<<"No way"<<endl;
}
return 0;
}L2-011 玩转二叉树
分数 25 作者 陈越 单位 浙江大学
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数\(N（≤30）\)，是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树反转后的层序遍历的序列。数字间以\(1\)个空格分隔，行首尾不得有多余空格。
输入样例：
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7输出样例：
4 6 1 7 5 3 2代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
240120
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 13 / 13 | |
| 1 | 384 | 3 | 答案正确 | 1 / 1 | |
| 2 | 312 | 3 | 答案正确 | 2 / 2 | |
| 3 | 316 | 3 | 答案正确 | 2 / 2 | |
| 4 | 316 | 3 | 答案正确 | 2 / 2 | |
| 5 | 440 | 3 | 答案正确 | 5 / 5 |
#include<bits/stdc++.h>
using namespace std;
struct tree{
int data;
tree* l;
tree* r;
};
tree* create(vector<int>& in,vector<int>& pre){
if(in.empty())
return NULL;
tree* now=new tree;
now->data=pre[0];
size_t len=find(in.begin(),in.end(),pre[0])-in.begin();
vector<int> in_l(in.begin(),in.begin()+len);
vector<int> pre_l(pre.begin()+1,pre.begin()+len+1);
vector<int> in_r(in.begin()+len+1,in.end());
vector<int> pre_r(pre.begin()+len+1,pre.end());
now->l=create(in_r,pre_r);
now->r=create(in_l,pre_l);
return now;
}
void space(){
static bool first=false;
if(first)
cout<<" ";
first=true;
}
void levelPrint(tree* root){
queue<tree*> q;
q.push(root);
while(!q.empty()){
tree* now=q.front();
q.pop();
space();
cout<<now->data;
if(now->l!=NULL)
q.push(now->l);
if(now->r!=NULL)
q.push(now->r);
}
cout<<endl;
}
int main(){
int n;
cin>>n;
vector<int> inorder(n);
vector<int> preorder(n);
for(int i=0;i<n;i++)
cin>>inorder[i];
for(int i=0;i<n;i++)
cin>>preorder[i];
tree* tr=create(inorder,preorder);
levelPrint(tr);
return 0;
}L2-014 列车调度
分数 25 作者 陈越 单位 浙江大学 火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式： 输入第一行给出一个整数N (2 ≤ N ≤10 5 )，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式： 在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例： 9 8 4 2 5 3 9 1 6 7 输出样例： 4 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB
Code
240121
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 4 | 答案正确 | 14 / 14 | |
| 1 | 11472 | 300 | 运行超时 | 0 / 2 | |
| 2 | 820 | 26 | 答案正确 | 2 / 2 | |
| 3 | 11464 | 300 | 运行超时 | 0 / 5 | |
| 4 | 324 | 3 | 答案正确 | 2 / 2 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,temp;
cin>>n;
vector<stack<int>> vs;
while(n--){
cin>>temp;
int cur=0;
while(cur<vs.size() && vs[cur].top()<temp){
cur++;
}
for(int i=cur+1;i<vs.size();i++){
if(vs[i].top()>temp && vs[cur].top()>vs[i].top()){
cur=i;
}
}
if(cur==vs.size()){
vs.emplace_back();
vs.back().push(temp);
}else{
vs[cur].push(temp);
}
}
// for(auto &v:vs){
// while(!v.empty()){
// cout<<v.top()<<" ";
// v.pop();
// }
// cout<<endl;
// }
cout<<vs.size()<<endl;
return 0;
}Code2
240121
去掉stack，其实只需要考虑top的值。因为之前爆了的两个点内存也非常大，所以优化了一下内存。
但是时间还是爆了。
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 14 / 14 | |
| 1 | 816 | 300 | 运行超时 | 0 / 2 | |
| 2 | 452 | 25 | 答案正确 | 2 / 2 | |
| 3 | 452 | 300 | 运行超时 | 0 / 5 | |
| 4 | 456 | 3 | 答案正确 | 2 / 2 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,temp,cur;
cin>>n;
vector<int> top;
while(n--){
cin>>temp;
cur=0;
while(cur<top.size() && top[cur]<temp){
cur++;
}
for(int i=cur+1;i<top.size();i++){
if(top[i]>temp && top[cur]>top[i]){
cur=i;
}
}
if(cur==top.size()){
top.push_back(temp);
}else{
top[cur]=temp;
}
}
cout<<top.size()<<endl;
return 0;
}Code3
240121
询问了GPT，居然有一个lower_bound的STL方法。
然后就，，，AC
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 320 | 2 | 答案正确 | 14 / 14 | |
| 1 | 1088 | 29 | 答案正确 | 2 / 2 | |
| 2 | 316 | 26 | 答案正确 | 2 / 2 | |
| 3 | 504 | 30 | 答案正确 | 5 / 5 | |
| 4 | 324 | 3 | 答案正确 | 2 / 2 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,temp;
cin>>n;
vector<int> top;
while(n--){
cin>>temp;
auto it=lower_bound(top.begin(),top.end(),temp);
if(it==top.end()){
top.push_back(temp);
} else{
*it=temp;
}
}
cout<<top.size()<<endl;
return 0;
}lower_bound函数
lower_bound
是一个在标准模板库（STL）中常用的函数，通常用于在一个已排序的范围内进行二分查找。它的目的是找到在范围内第一个不小于（即大于或等于）给定值的元素的位置。
下面是 lower_bound 函数内部逻辑的一个简化描述：
初始化指针或迭代器：函数开始时，设置两个指针或迭代器，分别指向要搜索的范围的起始和结束位置。
二分搜索：在搜索过程中，函数会不断将查找范围分为两半，选择其中一半继续搜索：
- 计算中间位置：首先，找到当前查找范围的中间位置。
- 比较中间元素与目标值：
- 如果中间元素小于目标值，搜索继续在中间元素之后的部分进行，因为我们正在寻找的是第一个不小于目标值的元素。
- 如果中间元素大于或等于目标值，搜索继续在中间元素以及之前的部分进行。
结束条件：当查找范围的开始位置超过或等于结束位置时，搜索结束。此时的开始位置就是第一个不小于目标值的元素的位置。如果所有元素都小于目标值，则该位置会是数组的末端。
返回结果：最终返回找到的位置的迭代器。
这种算法的时间复杂度是 ( O(n) )，其中 ( n ) 是搜索范围内的元素数量。由于它采用的是二分查找策略，因此在使用之前，必须确保范围内的元素是已排序的。
QA
Q
但是元素事实上并没有排序，可以使用lower_bound吗？
A
当使用 lower_bound
函数时，确实需要保证元素是按非降序排列的，也就是说，序列应该是排序的。在您的代码中，尽管原始输入数据可能未排序，但通过逐步构建的
top
向量实际上维护了一个有序序列。这个有序序列代表了目前为止找到的最长递增子序列的末端元素。
在这个过程中，每次当你使用 lower_bound 来查找
temp 的位置时，你其实是在查找在当前递增子序列中第一个不小于
temp 的位置。这允许你用 temp
替换找到的位置（如果有的话），从而维持这个递增序列的最小可能末端值。这个方法有效是因为它保留了递增序列的长度，同时使得后续有更大机会扩展这个序列。
因此，尽管原始输入可能未排序，你的算法通过维护 top
向量，保证了在每个时刻用于 lower_bound
搜索的序列都是有序的。这是最长递增子序列问题中常用的一种巧妙技术。
Thought
确实如此，如果我加入如下代码在循环中：
for(auto &i:top){
cout<<i<<" ";
}
cout<<endl;输出内容确实是这样的：
8
4
2
2 5
2 3
2 3 9
1 3 9
1 3 6
1 3 6 7是一个递增的子序列。
真的好神奇
L2-015 互评成绩
分数 25 作者 陈越 单位 浙江大学
学生互评作业的简单规则是这样定的：每个人的作业会被\(k\)个同学评审，得到\(k\)个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。
输入格式：
输入第一行给出3个正整数\(N\)（\(3 < N ≤10^4\)，学生总数）、\(k\)（\(3 ≤ k ≤ 10\)，每份作业的评审数）、\(M\)（\(≤ 20\)，需要输出的学生数）。随后\(N\)行，每行给出一份作业得到的\(k\)个评审成绩（在区间\([0, 100]\)内），其间以空格分隔。
输出格式：
按非递减顺序输出最后得分最高的M个成绩，保留小数点后\(3\)位。分数间有\(1\)个空格，行首尾不得有多余空格。
输入样例：
6 5 3
88 90 85 99 60
67 60 80 76 70
90 93 96 99 99
78 65 77 70 72
88 88 88 88 88
55 55 55 55 55输出样例：
87.667 88.000 96.000代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB
Code
240121
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 436 | 4 | 答案正确 | 15 / 15 | |
| 1 | 452 | 3 | 答案正确 | 2 / 2 | |
| 2 | 576 | 18 | 答案正确 | 2 / 2 | |
| 3 | 512 | 19 | 答案正确 | 6 / 6 |
#include<bits/stdc++.h>
using namespace std;
bool cmp(double& a,double& b){
return a>b;
}
int main(){
int n,k,m;
cin>>n>>k>>m;
vector<double> res;
while(n--){
vector<int> v(k);
for(int i=0;i<k;i++){
cin>>v[i];
}
sort(v.begin(),v.end());
int sum=0;
for(int i=1;i<k-1;i++){
sum+=v[i];
}
res.push_back(sum/(k-2.0));
}
sort(res.begin(),res.end(),cmp);
printf("%.3lf",res[m-1]);
for(int i=m-2;i>=0;i--){
printf(" %.3lf",res[i]);
}
printf("\n");
return 0;
}L2-016 愿天下有情人都是失散多年的兄妹
分数 25 作者 陈越 单位 浙江大学
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数\(N(2 ≤ N ≤10^4)\)，随后\(N\)行，每行按以下格式给出一个人的信息：
本人ID 性别 父亲ID 母亲ID其中\(ID\)是\(5\)位数字，每人不同；性别\(M\)代表男性、\(F\)代表女性。如果某人的父亲或母亲已经不可考，则相应的\(ID\)位置上标记为\(-1\)。
接下来给出一个正整数\(K\)，随后\(K\)行，每行给出一对有情人的\(ID\)，其间以空格分隔。
注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式：
对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。
输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
NoCode1
240122
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 1212 | 4 | 答案正确 | 15 / 15 | |
| 1 | 1220 | 4 | 答案错误 | 0 / 2 | |
| 2 | 1100 | 3 | 答案正确 | 2 / 2 | |
| 3 | 1092 | 13 | 答案错误 | 0 / 3 | |
| 4 | 1096 | 11 | 答案错误 | 0 / 3 |
#include<bits/stdc++.h>
using namespace std;
const int M=100000;
bool check(int a,int b);
int main(){
int n;
cin>>n;
int father[M];
int mather[M];
bool gender[M];
memset(father,-1,sizeof(father));
memset(mather,-1,sizeof(mather));
// for(int i=0;i<M;i++){
// member[i]=i+1;
// }
int id;
string gender_t;
for(int i=0;i<n;i++){
cin>>id;
cin>>gender_t;
gender[id]=(gender_t=="M")?true:false;
cin>>father[id];
cin>>mather[id];
}
int t,a,b;
cin>>t;
while(t--){
cin>>a>>b;
if(gender[a]==gender[b]){
cout<<"Never Mind"<<endl;
continue;
}
set<int> set1,set2;
set1.insert(a);
set2.insert(b);
bool flag=false;
int j;
for(j=0;j<4;j++){
set<int> set3,set4;
for(auto &k:set1){
// if(father[k]!=-1){
set3.insert(father[k]);
// }
// if(mather[k]!=-1){
set3.insert(mather[k]);
// }
}
for(auto &k:set2){
// if(father[k]!=-1){
set4.insert(father[k]);
// }
// if(mather[k]!=-1){
set4.insert(mather[k]);
// }
}
// for(auto &k:set3){
// cout<<k<<" ";
// }
// cout<<endl;
// for(auto &k:set4){
// cout<<k<<" ";
// }
// cout<<endl;
// cout<<endl;
for(auto &k:set4){
if(set3.find(k)!=set3.end() && k!=-1){
flag=true;
break;
}
}
if(flag){
break;
}
if(set3.find(-1)!=set3.end()){
set3.erase(-1);
}
if(set4.find(-1)!=set4.end()){
set4.erase(-1);
}
set1=set3;
set2=set4;
}
if(flag){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
}
return 0;
}
Code2
重新用dfs再写了一遍check2，但是还是只能A第一第三个点。
#include<bits/stdc++.h>
using namespace std;
const int M=100010;
// struct people{
// int father=-1;
// int mather=-1;
// bool gender=false;
// };
int father[M];
int mother[M];
bool gender[M];
bool dfs[M];
void read(int n){
int id;
string gender_t;
for(int i=0;i<n;i++){
cin>>id;
cin>>gender_t;
gender[id]=(gender_t=="M")?true:false;
cin>>father[id];
cin>>mother[id];
}
}
bool check(int a,int b){
set<int> set1,set2;
set1.insert(a);
set2.insert(b);
for(int i=0;i<4;i++){
set<int> set3=set1,set4=set2;
for(auto &k:set1){
set3.insert(father[k]);
set3.insert(mother[k]);
}
for(auto &k:set2){
set4.insert(father[k]);
set4.insert(mother[k]);
}
// for(auto &k:set3){
// cout<<k<<" ";
// }
// cout<<endl;
// for(auto &k:set4){
// cout<<k<<" ";
// }
// cout<<endl;
// cout<<endl;
if(set3.find(-1)!=set3.end())
set3.erase(-1);
if(set4.find(-1)!=set4.end())
set4.erase(-1);
for(auto &k:set4){
if(set3.find(k)!=set3.end()){
return false;
}
}
set1=set3;
set2=set4;
}
return true;
}
void dfs1(int x,int gen){
if(gen>4 || x==-1)
return;
dfs[x]=true;
dfs1(father[x],gen+1);
dfs1(mother[x],gen+1);
return;
}
bool dfs2(int x,int gen){
if(gen>4 || x==-1)
return false;
if(dfs[x]==true)
return true;
if(dfs2(father[x],gen+1) || dfs2(mother[x],gen+1))
return true;
return false;
}
bool check2(int a,int b){
dfs1(a,0);
if(dfs2(b,0))
return false;
return true;
}
int main(){
int n;
cin>>n;
memset(father,-1,sizeof(father));
memset(mother,-1,sizeof(mother));
read(n);
int t,a,b;
cin>>t;
while(t--){
cin>>a>>b;
memset(dfs,false,sizeof(dfs));
if(gender[a]==gender[b]){
cout<<"Never Mind"<<endl;
}else if(check2(a,b)){ //check1(a,b)也一样只A第一个和第三个点
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}Code3
240122
好好好，我是真的无语了。
把read函数改成这样就好了，忘了父母的性别。
void read(int n){
int id;
string gender_t;
for(int i=0;i<n;i++){
cin>>id;
cin>>gender_t;
gender[id]=(gender_t=="M")?true:false;
cin>>father[id];
gender[father[id]]=true;
cin>>mother[id];
gender[mother[id]]=false;
}
}L2-018 多项式A除以B
分数 25 作者 陈越 单位 浙江大学
这仍然是一道关于\(A/B\)的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商\(Q\)和余\(R\)，其中\(R\)的阶数必须小于\(B\)的阶数。
输入格式：
输入分两行，每行给出一个非零多项式，先给出\(A\)，再给出\(B\)。每行的格式如下：
N e[1] c[1] ... e[N] c[N]其中\(N\)是该多项式非零项的个数，e[i]是第\(i\)个非零项的指数，c[i]是第\(i\)个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。
输出格式：
分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后\(1\)位。同行数字间以\(1\)个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为0 0 0.0。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项-1/27，但因其舍入后为0.0，故不输出。
输入样例：
4 4 1 2 -3 1 -1 0 -1
3 2 3 1 -2 0 1输出样例：
3 2 0.3 1 0.2 0 -1.0
1 1 -3.1代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240122
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 4 | 答案正确 | 15 / 15 | |
| 1 | 448 | 4 | 答案正确 | 3 / 3 | |
| 2 | 448 | 5 | 运行时错误 | 0 / 3 | |
| 3 | 384 | 3 | 答案正确 | 3 / 3 | |
| 4 | 452 | 4 | 答案错误 | 0 / 1 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int na,nb,da,db;
cin>>na>>da;
vector<double> va(da+1);
cin>>va[da];
int temp;
for(int i=1;i<na;i++){
cin>>temp;
cin>>va[temp];
}
cin>>nb>>db;
vector<int> vb(db+1);
cin>>vb[db];
for(int i=1;i<nb;i++){
cin>>temp;
cin>>vb[temp];
}
int dc=da-db,nc=0;
vector<double> vc(dc+1);
int cur_a=da;
int cur_b=db;
int cur_c=dc;
// cout<<"*"<<endl;
// for(int i=0;i<da+1;i++){
// cout<<va[i]<<" ";
// }
// cout<<endl;
// for(int i=0;i<db+1;i++){
// cout<<vb[i]<<" ";
// }
// cout<<endl;
while(cur_c>=0){
vc[cur_c]=va[cur_a]/vb[db];
if(abs(vc[cur_c])>1e-6){
nc++;
va[cur_a]=0;
for(int i=1;i<db+1;i++){
va[cur_a-i]-=vb[db-i]*vc[cur_c];
}
}
// cout<<"va: ";
// for(auto &i:va){
// cout<<i<<" ";
// }
// cout<<endl;
// cout<<"vb: ";
// for(auto &i:vb){
// cout<<i<<" ";
// }
// cout<<endl;
// cout<<"vc: ";
// for(auto &i:vc){
// cout<<i<<" ";
// }
// cout<<endl<<endl;
cur_a--;
cur_b--;
cur_c--;
}
if(nc==0){
printf("0 0 0.0");
}else{
cout<<nc;
for(int i=dc;i>=0;i--){
if(abs(vc[i])>1e-6){
printf(" %d %.1lf",i,vc[i]);
}
}
}
printf("\n");
int nd=0;
for(int i=db-1;i>=0;i--){
if(abs(va[i])>=0.05){
nd++;
}
}
if(nd==0){
printf("0 0 0.0");
}else{
printf("%d",nd);
for(int i=db-1;i>=0;i--){
if(abs(va[i])>=0.05){
printf(" %d %.1lf",i,va[i]);
}
}
printf("\n");
}
return 0;
}Code2
240122 21:16
发现错误。如果第22行没有dc<0就会段错误。但是如果把等号加上，第四个测试点就会报错。
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 3 | 答案正确 | ||
| 1 | 460 | 3 | 答案正确 | ||
| 2 | 436 | 4 | 答案错误 | ||
| 3 | 384 | 3 | 答案正确 | ||
| 4 | 384 | 4 | 答案正确 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int na,nb,da,db;
cin>>na>>da;
vector<double> va(da+1,0.0);
cin>>va[da];
int temp;
for(int i=1;i<na;i++){
cin>>temp;
cin>>va[temp];
}
cin>>nb>>db;
vector<int> vb(db+1,0);
cin>>vb[db];
for(int i=1;i<nb;i++){
cin>>temp;
cin>>vb[temp];
}
// process
int dc=da-db;
if(dc<0){
cout<<"0 0 0.0"<<endl;
cout<<na;
for(int i=da;i>=0;i--){
if(abs(va[i])>1e-6){
cout<<" "<<i<<" "<<va[i];
}
}
cout<<endl;
return 0;
}
vector<double> vc(dc+1,0);
int cur_a=da;
int cur_c=dc;
while(cur_c>=0){
vc[cur_c]=va[cur_a]/vb[db];
if(abs(vc[cur_c])>1e-10){
va[cur_a]=0;
for(int i=1;i<db+1;i++){
va[cur_a-i]-=vb[db-i]*vc[cur_c];
}
}
cur_a--;
cur_c--;
}
// Output Line 1
int nc=0;
for(int i=dc;i>=0;i--){
if(abs(vc[i])>=0.05){
nc++;
}
}
if(nc==0){
printf("0 0 0.0\n");
}else{
cout<<nc;
for(int i=dc;i>=0;i--){
if(abs(vc[i])>=0.05){
printf(" %d %.1lf",i,vc[i]);
}
}
printf("\n");
}
// Output Line 2
int nd=0;
for(int i=db-1;i>=0;i--){
if(abs(va[i])>=0.05){
nd++;
}
}
if(nd==0){
printf("0 0 0.0\n");
}else{
printf("%d",nd);
for(int i=db-1;i>=0;i--){
if(abs(va[i])>=0.05){
printf(" %d %.1lf",i,va[i]);
}
}
printf("\n");
}
return 0;
}Code3
240122 21:43
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 476 | 3 | 答案正确 | 15 / 15 | |
| 1 | 308 | 3 | 答案正确 | 3 / 3 | |
| 2 | 324 | 4 | 答案正确 | 3 / 3 | |
| 3 | 452 | 3 | 答案正确 | 3 / 3 | |
| 4 | 324 | 3 | 答案正确 | 1 / 1 |
好好好，忘了输出的是浮点数。。
难怪A不了，就盯着看了一个小时。。
int dc=da-db;
if(dc<0){
printf("0 0 0.0\n");
printf("%d",na);
for(int i=da;i>=0;i--){
if(va[i]){
printf(" %d %.1lf",i,va[i]);
}
}
printf("\n");
return 0;
}L2-022 重排链表
分数 25 作者 陈越 单位 浙江大学
给定一个单链表 \(L_1→L_2→ \cdots →L_{n−1}→L_n\) ，请编写程序将链表重新排列为 \(L_n→L_1→L_{n−1}→L_2→\cdots\) 。例如：给定\(L\)为 \(1→2→3→4→5→6\)，则输出应该为 \(6→1→5→2→4→3\)。
输入格式：
每个输入包含 \(1\) 个测试用例。每个测试用例第 \(1\) 行给出第 \(1\) 个结点的地址和结点总个数，即正整数 \(N (≤10^5)\) 。结点的地址是 \(5\) 位非负整数，\(NULL\)地址用\(−1\)表示。
接下来有\(N\)行，每行格式为：
Address Data Next其中Address是结点地址；Data是该结点保存的数据，为不超过\(10^5\)的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1代码长度限制 16 KB 时间限制 500 ms 内存限制 64 MB
Code
240124
#include<bits/stdc++.h>
using namespace std;
const int M=100000;
struct Node{
int pre;
int data;
int next;
};
int main(){
Node node[M];
int head,tail,n;
cin>>head>>n;
node[head].pre=-1;
for(int i=0;i<n;i++){
int cur;
cin>>cur;
cin>>node[cur].data;
cin>>node[cur].next;
if(node[cur].next!=-1){
node[node[cur].next].pre=cur;
}else{
tail=cur;
}
}
// // Debug
// int cur2=head;
// while(cur2!=-1){
// cout<<"pre: "<<node[cur2].pre<<", id: "<<cur2<<", next: "<<node[cur2].next<<endl;
// cur2=node[cur2].next;
// }
Node res[M];
int res_head=tail;
int cur=res_head;
if(n%2==1){
while(head!=tail){
res[cur].data=node[tail].data;
res[cur].next=head;
cur=res[cur].next;
tail=node[tail].pre;
res[cur].data=node[head].data;
res[cur].next=tail;
cur=res[cur].next;
head=node[head].next;
}
res[cur].data=node[head].data;
res[cur].next=-1;
}else{
while(node[head].next!=tail){
res[cur].data=node[tail].data;
res[cur].next=head;
cur=res[cur].next;
tail=node[tail].pre;
res[cur].data=node[head].data;
res[cur].next=tail;
cur=res[cur].next;
head=node[head].next;
}
res[cur].data=node[tail].data;
res[cur].next=head;
res[head].data=node[head].data;
res[head].next=-1;
}
cur=res_head;
while(res[cur].next!=-1){
printf("%05d %d %05d\n",cur,res[cur].data,res[cur].next);
cur=res[cur].next;
}
printf("%05d %d %d\n",cur,res[cur].data,res[cur].next);
return 0;
}L2-023 图着色问题
分数 25 作者 陈越 单位 浙江大学
图着色问题是一个著名的\(NP\)完全问题。给定无向图\(G=(V,E)\)，问可否用\(K\)种颜色为\(V\)中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
输入格式：
输入在第一行给出3个整数 \(V（0<V≤500）\)、\(E（≥0）\)和\(K（0<K≤V）\)，分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从\(1\)到\(V\)编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数\(N（≤20）\)，是待检查的颜色分配方案的个数。随后\(N\)行，每行顺次给出\(V\)个顶点的颜色（第\(i\)个数字表示第\(i\)个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。
输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。
输入样例：
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4输出样例：
Yes
Yes
No
No代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB
Code1
240125
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 440 | 4 | 答案正确 | 15 / 15 | |
| 1 | 384 | 4 | 答案正确 | 2 / 2 | |
| 2 | 316 | 3 | 答案错误 | 0 / 2 | |
| 3 | 316 | 3 | 答案错误 | 0 / 2 | |
| 4 | 448 | 4 | 答案正确 | 1 / 1 | |
| 5 | 12088 | 149 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
bool check(vector<int>& colors,vector<set<int>>& graph,int v){
vector<int> painted(v+1,0);
for(int i=0;i<v;i++){
painted[i]=colors[i];
for(auto &t:graph[i]){
if(painted[t]==colors[i]){
return false;
}
}
}
return true;
}
int main(){
int v,e,k;
cin>>v>>e>>k;
vector<set<int>> graph(v+1);
for(int i=0;i<e;i++){
int src,dest;
cin>>src>>dest;
graph[src].insert(dest);
graph[dest].insert(src);
}
int c;
cin>>c;
while(c--){
set<int> color_count;
vector<int> colors;
for(int i=0;i<v;i++){
int temp;
cin>>temp;
color_count.insert(temp);
colors.push_back(temp);
}
if(check(colors,graph,v) && color_count.size()==k){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}Code2
240125
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 472 | 4 | 答案正确 | 15 / 15 | |
| 1 | 324 | 3 | 答案正确 | 2 / 2 | |
| 2 | 316 | 3 | 答案正确 | 2 / 2 | |
| 3 | 400 | 4 | 答案正确 | 2 / 2 | |
| 4 | 324 | 3 | 答案正确 | 1 / 1 | |
| 5 | 12096 | 157 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
vector<set<int>> graph(501);
int v;
bool check(vector<int>& colors){
for(int i=0;i<v;i++){
for(auto &t:graph[i]){
if(colors[t]==colors[i]){
return false;
}
}
}
return true;
}
int main(){
int e,k;
cin>>v>>e>>k;
for(int i=0;i<e;i++){
int src,dest;
cin>>src>>dest;
graph[src].insert(dest);
graph[dest].insert(src);
}
int c;
cin>>c;
while(c--){
set<int> color_count;
vector<int> colors(v+1);
for(int i=1;i<=v;i++){
cin>>colors[i];
color_count.insert(colors[i]);
}
if(check(colors) && color_count.size()==k){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}L2-024 部落
分数 25 作者 陈越 单位 浙江大学
在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数\(N（≤10^4）\)，是已知小圈子的个数。随后\(N\)行，每行按下列格式给出一个小圈子里的人：
\[ K P[1] P[2] ⋯ P[K] \]
其中\(K\)是小圈子里的人数，\(P[i]（i=1,⋯,K）\)是小圈子里每个人的编号。这里所有人的编号从\(1\)开始连续编号，最大编号不会超过\(10^4\)。
之后一行给出一个非负整数\(Q（≤10^4）\)，是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7输出样例：
10 2
Y
N代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB
Code
240125
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 436 | 3 | 答案正确 | 14 / 14 | |
| 1 | 448 | 4 | 答案正确 | 2 / 2 | |
| 2 | 324 | 3 | 答案正确 | 1 / 1 | |
| 3 | 952 | 26 | 答案正确 | 3 / 3 | |
| 4 | 832 | 26 | 答案正确 | 3 / 3 | |
| 5 | 312 | 3 | 答案正确 | 2 / 2 |
#include<bits/stdc++.h>
using namespace std;
const int M=10010;
int p[M];
void init(){
for(int i=0;i<M;i++){
p[i]=i;
}
}
int findfa(int n){
if(p[n]!=n){
p[n]=findfa(p[n]);
}
return p[n];
}
int main(){
int n;
cin>>n;
init();
set<int> all;
for(int i=0;i<n;i++){
int k;
cin>>k;
int v[k];
for(int j=0;j<k;j++){
cin>>v[j];
all.insert(v[j]);
}
int fa=findfa(v[0]);
for(int i=1;i<k;i++){
p[findfa(v[i])]=fa;
}
}
set<int> circle;
for(auto &i:all){
circle.insert(findfa(i));
}
cout<<all.size()<<" "<<circle.size()<<endl;
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
if(findfa(a)!=findfa(b)){
cout<<"N"<<endl;
}else{
cout<<"Y"<<endl;
}
}
return 0;
}L2-025 分而治之
分数 25 作者 陈越 单位 浙江大学
分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
输入格式：
输入在第一行给出两个正整数 \(N\) 和 \(M\)（均不超过\(10000\)），分别为敌方城市个数（于是默认城市从 \(1\) 到 \(N\) 编号）和连接两城市的通路条数。随后 \(M\) 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 \(K （≤ 100）\)和随后的 \(K\) 行方案，每行按以下格式给出： \[ Np v[1] v[2] ... v[Np] \] 其中 Np 是该方案中计划攻下的城市数量，后面的系列 \(v[i]\) 是计划攻下的城市编号。
输出格式：
对每一套方案，如果可行就输出YES，否则输出NO。
输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2输出样例：
NO
YES
YES
NO
NO代码长度限制 16 KB 时间限制 600 ms 内存限制 64 MB
Code
240125
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案错误 | 0 / 13 | |
| 1 | 436 | 3 | 答案正确 | 2 / 2 | |
| 2 | 1988 | 132 | 答案错误 | 0 / 5 | |
| 3 | 1976 | 122 | 答案错误 | 0 / 5 |
#include<iostream>
#include<vector>
#include<set>
using namespace std;
bool check(vector<set<int>>& city,vector<int> route){
for(int i=1;i<route.size();i++){
if(city[route[i-1]].find(route[i])==city[route[i-1]].end())
return false;
}
return true;
}
int main(){
int n,m;
cin>>n>>m;
vector<set<int>> city(n+1);
while(m--){
int src,dest;
cin>>src>>dest;
city[src].insert(dest);
city[dest].insert(src);
}
cin>>m;
while(m--){
int np;
cin>>np;
vector<int> v(np);
for(int i=0;i<np;i++)
cin>>v[i];
if(check(city,v))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}Code2
240126
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 4 | 答案正确 | 13 / 13 | |
| 1 | 316 | 3 | 答案正确 | 2 / 2 | |
| 2 | 2016 | 600 | 运行超时 | 0 / 5 | |
| 3 | 1968 | 600 | 运行超时 | 0 / 5 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
bool check(vector<set<int>>& city,vector<int> remove,int n){
for(int i=1;i<=n;i++){
if(find(remove.begin(),remove.end(),i)==remove.end()){
for(auto &k:city[i]){
if(find(remove.begin(),remove.end(),k)==remove.end()){
return false;
}
}
}
}
return true;
}
int main(){
int n,m;
cin>>n>>m;
vector<set<int>> city(n+1);
while(m--){
int src,dest;
cin>>src>>dest;
city[src].insert(dest);
city[dest].insert(src);
}
cin>>m;
while(m--){
int np;
cin>>np;
vector<int> v(np);
for(int i=0;i<np;i++)
cin>>v[i];
if(check(city,v,n))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}Code3
换set就好用了
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 3 | 答案正确 | 13 / 13 | |
| 1 | 320 | 3 | 答案正确 | 2 / 2 | |
| 2 | 2744 | 269 | 答案正确 | 5 / 5 | |
| 3 | 2744 | 256 | 答案正确 | 5 / 5 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n;
bool check(vector<set<int>>& city,set<int> remove){
for(int i=1;i<=n;i++){
if(remove.find(i)==remove.end()){
for(auto &k:city[i]){
if(remove.find(k)==remove.end()){
return false;
}
}
}
}
return true;
}
int main(){
int m;
cin>>n>>m;
vector<set<int>> city(n+1);
while(m--){
int src,dest;
cin>>src>>dest;
city[src].insert(dest);
city[dest].insert(src);
}
cin>>m;
while(m--){
int np,temp;
cin>>np;
set<int> s;
while(np--){
cin>>temp;
s.insert(temp);
}
if(check(city,s))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}L2-026 小字辈
分数 25 作者 陈越 单位 浙江大学
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 \(N\)（不超过 \(100000\) 的正整数） —— 简单起见，我们把家族成员从 \(1\) 到 \(N\) 编号。随后第二行给出 \(N\) 个编号，其中第 \(i\) 个编号对应第 \(i\) 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 \(-1\)。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 \(1\)，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9
2 6 5 5 -1 5 6 4 7输出样例：
4
1 9代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
20240126
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 436 | 3 | 答案正确 | 12 / 12 | |
| 1 | 2580 | 27 | 答案正确 | 3 / 3 | |
| 2 | 4344 | 28 | 答案正确 | 3 / 3 | |
| 3 | 324 | 3 | 答案正确 | 1 / 1 | |
| 4 | 6456 | 66 | 答案正确 | 1 / 1 | |
| 5 | 436 | 4 | 答案正确 | 2 / 2 | |
| 6 | 3888 | 53 | 答案正确 | 3 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n;
void dfs(vector<int>& tree,vector<int>& gen,int target){
int fa=tree[target];
if(fa==-1){
gen[target]=1;
}else if(gen[fa]!=0){
gen[target]=gen[fa]+1;
}else{
dfs(tree,gen,fa);
gen[target]=gen[fa]+1;
}
}
int main(){
cin>>n;
vector<int> v(n+1);
for(int i=1;i<=n;i++){
cin>>v[i];
}
vector<int> gen(n+1,0);
for(int i=1;i<=n;i++){
if(gen[i]==0){
dfs(v,gen,i);
}
}
int max=0;
set<int> s;
for(int i=1;i<=n;i++){
if(gen[i]>max){
max=gen[i];
s.clear();
s.insert(i);
}else if(gen[i]==max){
s.insert(i);
}
}
cout<<max<<endl;
bool isfirst=true;
for(auto &i:s){
if(!isfirst){
cout<<" ";
}
isfirst=false;
cout<<i;
}
cout<<endl;
return 0;
}L2-027 名人堂与代金券
分数 25 作者 陈越 单位 浙江大学
对于在中国大学MOOC（http://www.icourse163.org/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 \(60\) 分及以上，并且有另加福利：总评分在 \([G, 100]\) 区间内者，可以得到 \(50\) 元 PAT 代金券；在 \([60, G)\) 区间内者，可以得到 \(20\) 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 \(K\) 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。
输入格式：
输入在第一行给出 \(3\) 个整数，分别是 \(N\)（不超过 \(10000\) 的正整数，为学生总数）、\(G\)（在 \((60,100)\) 区间内的整数，为题面中描述的代金券等级分界线）、\(K\)（不超过 \(100\) 且不超过 \(N\) 的正整数，为进入名人堂的最低名次）。接下来 \(N\) 行，每行给出一位学生的账号（长度不超过\(15\)位、不带空格的字符串）和总评成绩（区间 \([0, 100]\) 内的整数），其间以空格分隔。题目保证没有重复的账号。
输出格式：
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 \(1\) 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。
输入样例：
10 80 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70输出样例：
360
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB
Code1
240126
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 13 / 13 | |
| 1 | 456 | 3 | 答案正确 | 3 / 3 | |
| 2 | 452 | 4 | 答案错误 | 0 / 3 | |
| 3 | 324 | 3 | 答案错误 | 0 / 2 | |
| 4 | 804 | 9 | 答案正确 | 4 / 4 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
struct student{
string name;
int score;
};
bool cmp(student& a,student& b){
if(a.score==b.score)
return a.name<b.name;
return a.score>b.score;
}
int main(){
int n,g,k,sum=0;
cin>>n>>g>>k;
vector<student> stu;
for(int i=0;i<n;i++){
string name;
int score;
cin>>name>>score;
if(score>=60){
stu.emplace_back();
stu.back().name=name;
stu.back().score=score;
if(score>=g){
sum+=50;
}else{
sum+=20;
}
}
}
cout<<sum<<endl;
sort(stu.begin(),stu.end(),cmp);
int count=0;
int last=0;
for(int i=0;i<stu.size();i++){
if(stu[i].score!=last){
count=0;
last=stu[i].score;
}else{
count+=1;
}
if(i+1-count>k){
break;
}
cout<<i+1-count<<" "<<stu[i].name<<" "<<stu[i].score<<endl;
}
return 0;
}Code2
240126
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 13 / 13 | |
| 1 | 452 | 4 | 答案正确 | 3 / 3 | |
| 2 | 468 | 4 | 答案正确 | 3 / 3 | |
| 3 | 456 | 3 | 答案正确 | 2 / 2 | |
| 4 | 1216 | 10 | 答案正确 | 4 / 4 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
struct student{
int rank=1;
string name;
int score;
};
bool cmp(student& a,student& b){
if(a.score==b.score)
return a.name<b.name;
return a.score>b.score;
}
int main(){
int n,g,k,sum=0;
cin>>n>>g>>k;
vector<student> stu;
for(int i=0;i<n;i++){
string name;
int score;
cin>>name>>score;
stu.emplace_back();
stu.back().name=name;
stu.back().score=score;
if(score>=g){
sum+=50;
}else if(score>=60){
sum+=20;
}
}
cout<<sum<<endl;
sort(stu.begin(),stu.end(),cmp);
for(int i=1;i<stu.size();i++){
if(stu[i].score!=stu[i-1].score){
stu[i].rank=i+1;
}else{
stu[i].rank=stu[i-1].rank;
}
}
int count=0;
int last=0;
for(auto &i:stu){
if(i.rank>k){
break;
}
cout<<i.rank<<" "<<i.name<<" "<<i.score<<endl;
}
return 0;
}L2-029 特立独行的幸福
分数 25 作者 陈越 单位 浙江大学
对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 \(1\)，就称该数为幸福数。\(1\) 是一个幸福数。此外，例如 \(19\) 经过 \(1\) 次迭代得到 \(82\)，\(2\) 次迭代后得到 \(68\)，\(3\) 次迭代后得到 \(100\)，最后得到 \(1\)。则 \(19\) 就是幸福数。显然，在一个幸福数迭代到 \(1\) 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 \(82\)、\(68\)、\(100\) 的幸福是依附于 \(19\) 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如 \(19\) 在区间\([1, 100]\) 内就是一个特立独行的幸福数，其独立性为 \(2×4=8\)。
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 \(29\) 迭代得到 \(85、89、145、42、20、4、16、37、58、89、……\) 可见 \(89\) 到 \(58\) 形成了死循环，所以 \(29\) 就不幸福。
本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。
输入格式：
输入在第一行给出闭区间的两个端点：\(1<A<B≤10^4\).
输出格式：
按递增顺序列出给定闭区间 \([A,B]\) 内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以 \(1\) 个空格分隔。
如果区间内没有幸福数，则在一行中输出 SAD。
输入样例 1：
10 40输出样例 1：
19 8
23 6
28 3
31 4
32 3注意：样例中，\(10、13\) 也都是幸福数，但它们分别依附于其他数字（如 \(23、31\) 等等），所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间 \([10, 40]\) 内，所以它们在给定区间内是特立独行的幸福数。
输入样例 2：
110 120输出样例 2：
SAD代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code
240127
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 4 | 答案正确 | 12 / 12 | |
| 1 | 312 | 3 | 答案正确 | 1 / 1 | |
| 2 | 332 | 3 | 答案正确 | 1 / 1 | |
| 3 | 328 | 3 | 答案正确 | 2 / 2 | |
| 4 | 320 | 3 | 答案正确 | 3 / 3 | |
| 5 | 448 | 11 | 答案正确 | 6 / 6 |
#include<iostream>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
int next(int n){
int res=0;
while(n>0){
res+=(n%10)*(n%10);
n/=10;
}
return res;
}
bool isprime(int n){
if(n<=1) return false;
if(n==2) return true;
if(n%2==0) return false;
for(int i=3;i<sqrt(n)+1;i+=2){
if(n%i==0) return false;
}
return true;
}
int a,b;
int check(int n){
set<int> s;
s.insert(n);
n=next(n);
while(n!=1){
if(n>=a && n<=b) return -1;
if(s.find(n)!=s.end()) return -1;
s.insert(n);
n=next(n);
}
if(n==1) return s.size();
return -1;
}
set<int> findluck(){
set<int> luck;
for(int i=a;i<=b;i++){
int now=i;
set<int> s;
while(now!=1 && s.find(now)==s.end()){
s.insert(now);
now=next(now);
}
if(now==1){
luck.insert(i);
}
}
return luck;
}
// set<int> findDluck(){
// set<int> lucknum;
// set<int> Dlucknum;
// for(int i=a;i<=b;i++){
// int now=i;
// cout<<"&"<<i<<endl;
// set<int> s;
// now=next(now);
// while(now!=1 && s.find(now)==s.end()){
// s.insert(now);
// now=next(now);
// // cout<<now<<endl;
// }
// if(now==1){
// int flag=true;
// for(auto &k:s){
// if(k>=a && k<=b){
// flag=false;
// break;
// }
// }
// if(flag){
// Dlucknum.insert(i);
// for(auto &k:s){
// Dlucknum.erase(k);
// lucknum.insert(k);
// }
// }else{
// lucknum.insert(i);
// for(auto &k:s){
// lucknum.insert(k);
// }
// }
// }
// }
// for(auto &k:lucknum){
// cout<<k<<endl;
// }
// cout<<"*"<<endl;
// return Dlucknum;
// }
vector<pair<int,int>> findDluck(set<int> lucknum){
set<int> notDlucknum;
for(auto &k:lucknum){
int now=next(k);
while(now!=1){
if(lucknum.find(now)!=lucknum.end()){
notDlucknum.insert(now);
}
now=next(now);
}
}
vector<pair<int,int>> Dlucknum;
for(auto &k:lucknum){
if(notDlucknum.find(k)==notDlucknum.end()){
int independence=0;
int temp=k;
while(temp!=1){
temp=next(temp);
independence++;
}
if(isprime(k)){
independence*=2;
}
Dlucknum.push_back(make_pair(k,independence));
}
}
return Dlucknum;
}
int main(){
cin>>a>>b;
set<int> lucknum=findluck();
vector<pair<int,int>> Dlucknum=findDluck(lucknum);
if(Dlucknum.empty()){
cout<<"SAD"<<endl;
}else{
for(auto &k:Dlucknum){
cout<<k.first<<" "<<k.second<<endl;
}
}
// for(int i=a;i<=b;i++){
// int t=check(i);
// if(t!=-1){
// if(isprime(i)){
// t*=2;
// }
// cout<<i<<" "<<t<<endl;
// }
// }
return 0;
}L2-030 冰岛人
分数 25 作者 陈越 单位 浙江大学
2018年世界杯，冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”（son），于是有网友科普如下：
冰岛人沿用的是维京人古老的父系姓制，孩子的姓等于父亲的名加后缀，如果是儿子就加
sson，女儿则加
sdottir。因为冰岛人口较少，为避免近亲繁衍，本地人交往前先用个
App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。
输入格式：
输入首先在第一行给出一个正整数 \(N（1<N≤10^5）\)，为当地人口数。随后
\(N\)
行，每行给出一个人名，格式为：名 姓（带性别后缀），两个字符串均由不超过
\(20\)
个小写的英文字母组成。维京人后裔是可以通过姓的后缀判断其性别的，其他人则是在姓的后面加
\(m\) 表示男性、\(f\)
表示女性。题目保证给出的每个维京家族的起源人都是男性。
随后一行给出正整数 \(M\)，为查询数量。随后 \(M\)
行，每行给出一对人名，格式为：名1 姓1 名2 姓2。注意：这里的姓是不带后缀的。四个字符串均由不超过
\(20\) 个小写的英文字母组成。
题目保证不存在两个人是同名的。
输出格式：
对每一个查询，根据结果在一行内显示以下信息：
- 若两人为异性，且五代以内无公共祖先，则输出
Yes； - 若两人为异性，但五代以内（不包括第五代）有公共祖先，则输出
No； - 若两人为同性，则输出
Whatever； - 若有一人不在名单内，则输出
NA。
所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。
输入样例：
15
chris smithm
adam smithm
bob adamsson
jack chrissson
bill chrissson
mike jacksson
steve billsson
tim mikesson
april mikesdottir
eric stevesson
tracy timsdottir
james ericsson
patrick jacksson
robin patricksson
will robinsson
6
tracy tim james eric
will robin tracy tim
april mike steve bill
bob adam eric steve
tracy tim tracy tim
x man april mikes输出样例：
Yes
No
No
Whatever
Whatever
NA代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240127
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 440 | 4 | 答案正确 | 12 / 12 | |
| 1 | 328 | 3 | 答案正确 | 2 / 2 | |
| 2 | 388 | 3 | 答案正确 | 2 / 2 | |
| 3 | 448 | 3 | 答案错误 | 0 / 2 | |
| 4 | 316 | 3 | 答案错误 | 0 / 1 | |
| 5 | 14384 | 75 | 答案正确 | 3 / 3 | |
| 6 | 14396 | 84 | 答案错误 | 0 / 3 |
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<set>
using namespace std;
struct people{
bool gender; // true->male
bool isviking; // true->yes
string firstname;
string lastname;
};
int main(){
int n;
cin>>n;
map<string,people> m;
for(int i=0;i<n;i++){
people peo;
string firstname,lastname;
bool gender,isviking;
cin>>firstname;
cin>>lastname;
if(lastname.back()=='m'){
isviking=false;
gender=true;
lastname.pop_back();
lastname=lastname;
}else if(lastname.back()=='f'){
isviking=false;
gender=false;
lastname.pop_back();
lastname=lastname;
}else if(lastname.rfind("sdottir")!=string::npos){
lastname.erase(lastname.find("sdottir"),strlen("sdottir"));
isviking=true;
gender=false;
lastname=lastname;
}else{
lastname.erase(lastname.find("sson"),strlen("sson"));
isviking=true;
gender=true;
lastname=lastname;
}
peo.firstname=firstname;
peo.lastname=lastname;
peo.gender=gender;
peo.isviking=isviking;
m[firstname]=peo;
}
int c;
cin>>c;
while(c--){
string f1,l1,f2,l2;
cin>>f1>>l1>>f2>>l2;
if(m.find(f1)!=m.end() && m.find(f2)!=m.end()){
if(m[f1].gender!=m[f2].gender){
bool marryable=true;
set<string> ance1;
string fa=f1;
for(int i=0;i<3;i++){
if(m.find(fa)!=m.end()){
fa=m[fa].lastname;
ance1.insert(fa);
}else{
break;
}
}
set<string> ance2;
fa=f2;
for(int i=0;i<3;i++){
if(m.find(fa)!=m.end()){
fa=m[fa].lastname;
if(ance1.find(fa)!=ance1.end()){
marryable=false;
break;
}
}else{
break;
}
}
// cout<<"&"<<endl;
// for(auto &k:ance1){
// cout<<k<<" ";
// }cout<<endl;
// for(auto &k:ance2){
// cout<<k<<" ";
// }cout<<endl;
// for(auto &k:ance1){
// if(ance2.find(k)!=ance2.end()){
// marryable=false;
// break;
// }
// }
if(marryable){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}else{
cout<<"Whatever"<<endl;
}
}else{
cout<<"NA"<<endl;
}
}
return 0;
}Code2
240127
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 12 / 12 | |
| 1 | 460 | 3 | 答案正确 | 2 / 2 | |
| 2 | 448 | 3 | 答案正确 | 2 / 2 | |
| 3 | 312 | 3 | 答案正确 | 2 / 2 | |
| 4 | 328 | 3 | 答案正确 | 1 / 1 | |
| 5 | 11332 | 68 | 答案正确 | 3 / 3 | |
| 6 | 11360 | 269 | 答案正确 | 3 / 3 |
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<set>
using namespace std;
map<string,pair<bool,string>> m;
set<string> getAnce(string name){
set<string> ance;
for(int i=0;i<3;i++){
ance.insert(m[name].second);
name=m[name].second;
if(name==""){
break;
}
}
return ance;
}
string check(string name1,string name2){
int cnt1=0,cnt2;
while(name1!=""){
cnt2=0;
string name=name2;
while(name!=""){
if(name==name1 && (cnt1<4 || cnt2<4)) return "No";
if(cnt1>=4 && cnt2>=4) return "Yes";
name=m[name].second;
cnt2++;
}
cnt1++;
name1=m[name1].second;
}
return "Yes";
}
int main(){
int n;
cin>>n;
while(n--){
string firstname,lastname;
bool gender;
cin>>firstname;
cin>>lastname;
if(lastname.back()=='m'){
m[firstname].first=true;
}else if(lastname.back()=='f'){
m[firstname].first=false;
}else if(lastname.back()=='r'){
m[firstname].second=lastname.erase(lastname.rfind("sdottir"));
m[firstname].first=false;
}else{
m[firstname].second=lastname.erase(lastname.rfind("sson"));
m[firstname].first=true;
}
}
int c;
cin>>c;
while(c--){
string f1,l1,f2,l2;
cin>>f1>>l1>>f2>>l2;
if(m.find(f1)==m.end() || m.find(f2)==m.end())
cout<<"NA"<<endl;
else if(m[f1].first==m[f2].first)
cout<<"Whatever"<<endl;
else{
cout<<check(f1,f2)<<endl;
// bool marryable=true;
// set<string> ance1=getAnce(f1);
// set<string> ance2=getAnce(f2);
// for(auto &k:ance2){
// if(ance1.find(k)!=ance1.end()){
// marryable=false;
// break;
// }
// }
// if(marryable){
// cout<<"Yes"<<endl;
// }else{
// cout<<"No"<<endl;
// }
}
}
return 0;
}L2-031 深入虎穴
分数 25 作者 陈越 单位 浙江大学
著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。
输入格式：
输入首先在一行中给出正整数 \(N（<10^5）\)，是门的数量。最后 \(N\) 行，第 \(i\) 行\(（1≤i≤N）\)按以下格式描述编号为 \(i\) 的那扇门背后能通向的门：
K D[1] D[2] ... D[K]其中 \(K\) 是通道的数量，其后是每扇门的编号。
输出格式：
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。
输入样例：
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0输出样例：
12代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240127
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 460 | 3 | 答案正确 | 12 / 12 | |
| 1 | 456 | 3 | 答案正确 | 1 / 1 | |
| 2 | 5864 | 42 | 答案错误 | 0 / 3 | |
| 3 | 65536 | 109 | 内存超限 | 0 / 2 | |
| 4 | 464 | 3 | 答案错误 | 0 / 2 | |
| 5 | 47136 | 400 | 运行超时 | 0 / 2 | |
| 6 | 65536 | 100 | 内存超限 | 0 / 3 |
#include<iostream>
#include<queue>
using namespace std;
int max_depth=0,door;
void dfs(vector<vector<int>> v,int depth,int now){
if(depth>max_depth){
max_depth=depth;
door=now;
}
for(int i=0;i<v[now].size();i++){
dfs(v,depth+1,v[now][i]);
}
}
int main(){
int n;
cin>>n;
vector<vector<int>> v(1);
while(n--){
v.emplace_back();
int k;
cin>>k;
while(k--){
int t;
cin>>t;
v.back().push_back(t);
}
}
dfs(v,1,1);
cout<<door<<endl;
return 0;
}Code2
240127
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 3 | 答案正确 | 12 / 12 | |
| 1 | 448 | 3 | 答案正确 | 1 / 1 | |
| 2 | 9664 | 63 | 答案错误 | 0 / 3 | |
| 3 | 9780 | 49 | 答案正确 | 2 / 2 | |
| 4 | 316 | 3 | 答案错误 | 0 / 2 | |
| 5 | 9912 | 50 | 答案错误 | 0 / 2 | |
| 6 | 10296 | 55 | 答案正确 | 3 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;
int max_depth = 0, door = 1;
void bfs(vector<set<int>>& v) {
queue<pair<int, int>> q;
q.push(make_pair(1, 1));
while (!q.empty()) {
int now = q.front().first;
int depth = q.front().second;
q.pop();
if (depth > max_depth) {
max_depth = depth;
door = now;
}
for (int k : v[now]) {
q.push(make_pair(k, depth + 1));
}
}
}
int main() {
int n;
cin >> n;
vector<set<int>> v(n + 1);
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
while (k--) {
int t;
cin >> t;
v[i].insert(t);
}
}
bfs(v);
cout << door << endl;
return 0;
}Code3
240127
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 12 / 12 | |
| 1 | 328 | 3 | 答案正确 | 1 / 1 | |
| 2 | 19116 | 108 | 答案正确 | 3 / 3 | |
| 3 | 19164 | 114 | 答案正确 | 2 / 2 | |
| 4 | 448 | 3 | 答案正确 | 2 / 2 | |
| 5 | 19168 | 94 | 答案正确 | 2 / 2 | |
| 6 | 19228 | 124 | 答案正确 | 3 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;
int max_depth=0,door=1;
vector<set<int>> v(1);
set<int> used;
void graph(){
for(int i=1;i<v.size();i++){
for(auto &k:v[i]){
v[k].insert(i);
}
}
}
void bfs(){
queue<pair<int,int>> q;
q.push(make_pair(1,1));
while(!q.empty()){
int now=q.front().first;
int depth=q.front().second;
q.pop();
used.insert(now);
if(depth>max_depth){
max_depth=depth;
door=now;
}
for(auto &k:v[now]){
if(used.find(k)==used.end())
q.push(make_pair(k,depth+1));
}
}
}
int main(){
int n;
cin>>n;
while(n--){
v.emplace_back();
int k,t;
cin>>k;
while(k--){
cin>>t;
v.back().insert(t);
}
}
graph();
bfs();
cout<<door<<endl;
return 0;
}L2-032 彩虹瓶
分数 25 作者 陈越 单位 浙江大学
彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。
假设彩虹瓶里要按顺序装 \(N\) 种颜色的小球（不妨将顺序就编号为 \(1\) 到 \(N\)）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。
如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6 两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1 时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6 上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7 依次装填。
但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货，工人就必须要愤怒地折腾货架了，因为装填完 2 号颜色以后，不把货架上的多个箱子搬下来就拿不到 3 号箱，就不可能顺利完成任务。
另外，货架的容量有限，如果要堆积的货物超过容量，工人也没办法顺利完成任务。例如工厂按照 7、6、5、4、3、2、1 这个顺序发货，如果货架够高，能码放 6 只箱子，那还是可以顺利完工的；但如果货架只能码放 5 只箱子，工人就又要愤怒了……
本题就请你判断一下，工厂的发货顺序能否让工人顺利完成任务。
输入格式：
输入首先在第一行给出 \(3\) 个正整数，分别是彩虹瓶的颜色数量 \(N（1<N≤10^3）\)、临时货架的容量 \(M（<N）\)、以及需要判断的发货顺序的数量 \(K\)。
随后 \(K\) 行，每行给出 \(N\) 个数字，是 \(1\) 到 \(N\) 的一个排列，对应工厂的发货顺序。
一行中的数字都以空格分隔。
输出格式：
对每个发货顺序，如果工人可以愉快完工，就在一行中输出
YES；否则输出 NO。
输入样例：
7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1输出样例：
YES
NO
NO代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240128
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 444 | 3 | 答案错误 | 0 / 15 | |
| 1 | 324 | 3 | 答案错误 | 0 / 3 | |
| 2 | 408 | 3 | 答案错误 | 0 / 2 | |
| 3 | 324 | 3 | 答案正确 | 2 / 2 | |
| 4 | 444 | 3 | 答案正确 | 1 / 1 | |
| 5 | 316 | 3 | 答案错误 | 0 / 2 |
#include<iostream>
#include<set>
using namespace std;
bool check(int n,int m){
set<int> s;
int temp,count=1;
while(count<=n){
if(s.find(count)!=s.end()){
s.erase(count);
count++;
}else{
cin>>temp;
if(temp!=count){
s.insert(temp);
}else{
count++;
}
}
if(s.size()>m){
return false;
}
}
return true;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
while(k--){
if(check(n,m)){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}Code2
240128
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 4 | 答案错误 | 0 / 15 | |
| 1 | 332 | 3 | 答案正确 | 3 / 3 | |
| 2 | 320 | 3 | 答案错误 | 0 / 2 | |
| 3 | 384 | 4 | 答案正确 | 2 / 2 | |
| 4 | 316 | 3 | 答案正确 | 1 / 1 | |
| 5 | 320 | 3 | 答案错误 | 0 / 2 |
#include<iostream>
#include<stack>
using namespace std;
bool check(int n,int m){
stack<int> s;
int temp,count=1;
while(count<=n){
if(!s.empty() && s.top()==count){
s.pop();
count++;
}else{
cin>>temp;
if(temp!=count){
s.push(temp);
}else{
count++;
}
}
if(s.size()>m){
return false;
}
}
return true;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
while(k--){
if(check(n,m)){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}Code3
240128
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 488 | 3 | 答案错误 | 0 / 15 | |
| 1 | 312 | 4 | 答案正确 | 3 / 3 | |
| 2 | 440 | 3 | 答案正确 | 2 / 2 | |
| 3 | 332 | 3 | 答案正确 | 2 / 2 | |
| 4 | 460 | 4 | 答案正确 | 1 / 1 | |
| 5 | 328 | 3 | 答案正确 | 2 / 2 |
#include<iostream>
#include<stack>
using namespace std;
bool check(int n,int m){
stack<int> s;
int temp,need=1;
while(n--){
cin>>temp;
if(temp==need){
need++;
while(!s.empty() && s.top()==need){
s.pop();
need++;
}
}else{
s.push(temp);
if(s.size()>m) return false;
}
}
if(s.empty()) return true;
else return false;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
while(k--){
if(check(n,m)){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}Code4
240128
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 15 / 15 | |
| 1 | 456 | 4 | 答案正确 | 3 / 3 | |
| 2 | 476 | 3 | 答案正确 | 2 / 2 | |
| 3 | 332 | 4 | 答案正确 | 2 / 2 | |
| 4 | 444 | 4 | 答案正确 | 1 / 1 | |
| 5 | 444 | 3 | 答案正确 | 2 / 2 |
如果在处理过程中出现货架上货物超限，那么就标记答案为为false，此时不要急着退出循环，因为当前的询问的输入操作还未结束。如果最后货架上还有货物没发货，那么也标记答案为false。
#include<iostream>
#include<stack>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
while(k--){
int temp,need=1;
stack<int> s;
bool flag=true;
for(int i=0;i<n;i++){
cin>>temp;
if(temp==need){
need++;
while(!s.empty() && s.top()==need){
s.pop();
need++;
}
}else{
s.push(temp);
}
if(s.size()>m){
flag=false;
}
}
if(s.size()>0){
flag=false;
}
cout<<(flag?"YES":"NO")<<endl;
}
return 0;
}L2-036 网红点打卡攻略
分数 25 作者 陈越 单位 浙江大学
一个旅游景点，如果被带火了的话，就被称为“网红点”。大家来网红点游玩，俗称“打卡”。在各个网红点打卡的快（省）乐（钱）方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
输入格式：
首先第一行给出两个正整数：网红点的个数 \(N（1<N≤200）\) 和网红点之间通路的条数
\(M\)。随后 \(M\)
行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1 网红点2 费用”，其中网红点从
\(1\) 到 \(N\)
编号；同时也给出你家到某些网红点的花费，格式相同，其中你家的编号固定为
\(0\)。
再下一行给出一个正整数 \(K\)，是待检验的攻略的数量。随后 \(K\) 行，每行给出一条待检攻略，格式为：
\[ n,V_1,V_2,\cdots,V_n \]
其中 \(n(≤200)\) 是攻略中的网红点数， \(V_i\) 是路径上的网红点编号。这里假设你从家里出发，从 \(V_1\) 开始打卡，最后从 \(V_n\) 回家。
输出格式：
在第一行输出满足要求的攻略的个数。
在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从 \(1\) 开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。
题目保证至少存在一个有效攻略，并且总路费不超过\(10^9\)。
输入样例：
6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6输出样例：
3
5 11样例说明：
第 \(2\)、\(3\)、\(4\)、\(6\) 条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有 \(3\) 条。
第 \(1\) 条攻略的总路费是：\((0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14\)；
第 \(5\) 条攻略的总路费同理可算得：\(1 + 1 + 1 + 2 + 3 + 1 + 2 = 11\)，是一条更省钱的攻略；
第 \(7\) 条攻略的总路费同理可算得：\(2 + 1 + 1 + 2 + 2 + 2 + 1 = 11\)，与第 \(5\) 条花费相同，但序号较大，所以不输出。
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 588 | 3 | 答案正确 | 15 / 15 | |
| 1 | 604 | 3 | 答案正确 | 3 / 3 | |
| 2 | 548 | 3 | 答案错误 | 0 / 3 | |
| 3 | 564 | 3 | 答案正确 | 1 / 1 | |
| 4 | 1464 | 43 | 答案错误 | 0 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int route[201][201];
memset(route,-1,sizeof(route));
while(m--){
int a,b,c;
cin>>a>>b>>c;
route[a][b]=c;
route[b][a]=c;
}
cin>>m;
int count=0,mincost=10000,minroute=0;
for(int i=1;i<=m;i++){
bool used[n+1];
memset(used,false,sizeof(used));
int cost=0,c;
cin>>c;
int r[c];
for(int j=0;j<c;j++){
cin>>r[j];
}
// cout<<"&"<<endl;
if(c!=n) continue;
int now=0;
bool flag=true;
for(int j=0;j<c;j++){
if(route[now][r[j]]==-1 && !used[r[j]]) flag=false;
else cost+=route[now][r[j]];
now=r[j];
used[r[j]]=true;
}
if(route[now][0]==-1) flag=false;
cost+=route[now][0];
if(flag){
count++;
}
if(flag && cost<mincost){
mincost=cost;
minroute=i;
}
}
cout<<count<<endl;
cout<<minroute<<" "<<mincost<<endl;
return 0;
}Code2
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 444 | 3 | 答案正确 | 15 / 15 | |
| 1 | 588 | 3 | 答案正确 | 3 / 3 | |
| 2 | 452 | 4 | 答案正确 | 3 / 3 | |
| 3 | 452 | 3 | 答案正确 | 1 / 1 | |
| 4 | 572 | 44 | 答案错误 | 0 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int route[201][201];
memset(route,-1,sizeof(route));
while(m--){
int a,b,c;
cin>>a>>b>>c;
route[a][b]=c;
route[b][a]=c;
}
cin>>m;
int count=0,mincost=10000,minroute=0;
for(int i=1;i<=m;i++){
bool used[n+1];
memset(used,false,sizeof(used));
int cost=0,c;
cin>>c;
int r[c];
for(int j=0;j<c;j++){
cin>>r[j];
}
// cout<<"&"<<endl;
if(c!=n) continue;
int now=0;
bool flag=true;
for(int j=0;j<c;j++){
if(route[now][r[j]]==-1 || used[r[j]]) flag=false;
cost+=route[now][r[j]];
used[now]=true;
now=r[j];
}
if(route[now][0]==-1 || used[now]) flag=false;
cost+=route[now][0];
if(flag){
count++;
if(cost<mincost){
mincost=cost;
minroute=i;
}
}
}
cout<<count<<endl;
cout<<minroute<<" "<<mincost<<endl;
return 0;
}Code3
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 580 | 4 | 答案正确 | 15 / 15 | |
| 1 | 572 | 3 | 答案正确 | 3 / 3 | |
| 2 | 448 | 3 | 答案正确 | 3 / 3 | |
| 3 | 512 | 3 | 答案正确 | 1 / 1 | |
| 4 | 456 | 44 | 答案正确 | 3 / 3 |
最后发现是mincost不够大，需要0x3f3f3f3f才够。
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int route[210][210];
memset(route,0,sizeof(route));
while(m--){
int a,b,c;
cin>>a>>b>>c;
route[a][b]=c;
route[b][a]=c;
}
cin>>m;
int count=0,mincost=0x3f3f3f3f,minroute=0;
bool used[210];
for(int i=1;i<=m;i++){
memset(used,false,sizeof(used));
int cost=0,c,now=0,next;
bool flag=true;
cin>>c;
// cout<<"&"<<endl;
for(int j=0;j<c;j++){
cin>>next;
if(route[now][next]==0||used[next]) flag=false;
else cost+=route[now][next];
used[now]=true;
now=next;
}
if(route[now][0]==0||used[now]) flag=false;
else cost+=route[now][0];
if(flag&&c==n){
count++;
if(cost<mincost){
mincost=cost;
minroute=i;
}
}
}
cout<<count<<endl;
cout<<minroute<<" "<<mincost<<endl;
return 0;
}QA
Q
为什么我的代码在第11行命名route的时候，大小设置为2100*2100后，运行代码会出现段错误。我能够保证输入时合法的，因为route在设置成210*210时不会出现段错误。
A
当您尝试将 route 数组的大小设置为
2100 x 2100 时，出现段错误（segmentation
fault）的原因通常是由于栈溢出。在 C++ 中，默认情况下，局部变量（如您的
route
数组）是在栈上分配的，而栈空间是有限的。对于大多数系统，栈的大小通常是几个
MB（通常在 1MB 到 8MB 之间），这意味着您不能在栈上分配太大的数组。
int 类型通常占用 4
个字节（这可能因编译器和平台而异）。因此，一个 2100 x 2100
的 int 数组将占用大约 2100 * 2100 * 4
字节，即约
17.5MB。这超过了大多数系统栈的大小限制，因此会导致栈溢出和段错误。
要解决这个问题，您可以考虑以下几种方法：
动态分配内存：使用
std::vector或手动使用new关键字在堆上分配数组。堆的大小远大于栈，通常是几个 GB，因此可以分配更大的数组。例如，您可以使用vector如下所示：vector<vector<int>> route(2100, vector<int>(2100, 0));调整系统的栈大小：这通常不推荐，因为它依赖于操作系统的特定配置，并且可能导致程序在不同环境下行为不一致。
减小数组大小：如果可能，考虑是否真的需要那么大的数组。有时候，对问题的重新思考可以找到使用较小数据结构的方法。
优化数据结构：如果您的应用场景允许，可以考虑使用其他数据结构（如图或邻接表）来存储数据，这样可能会更加节省空间。
在大多数情况下，选择动态内存分配（使用 std::vector 或
new）是处理大数组的最佳方法。
堆和栈
堆（Heap）和栈（Stack）是计算机内存中用于存储数据的两种重要区域，它们在数据存储和管理方面有各自的特点和用途。理解它们的区别对于编程尤其重要，因为它们影响了程序的性能和方式。
栈（Stack）
内存管理：栈是由操作系统自动管理的内存区域。当函数被调用时，其局部变量就会被分配在栈上。
大小限制：栈的大小通常有限。在大多数现代操作系统中，栈大小是固定的，一般为几百 KB 到几 MB。
访问速度：访问栈内存非常快，因为它具有连续的内存结构，且栈顶的地址是已知的。
生命周期：栈上的对象通常具有自动存储期。一旦创建函数的执行上下文（如函数调用），局部变量就会被创建；当上下文结束时（如函数返回），这些局部变量就会被销毁。
适用场景：适合存储函数参数、返回地址和局部变量。
堆（Heap）
内存管理：堆是由程序员手动管理的内存区域（在某些语言中，如Java和Python，由垃圾回收器管理）。当需要在程序的任何部分动态地分配内存时，会使用堆。
大小限制：堆的大小通常受到系统可用内存的限制，远大于栈。它可以用于分配大量的内存，如大数组和大对象。
访问速度：访问堆内存通常比访问栈内存慢，因为堆是在全局内存池中动态分配的。
生命周期：堆上的对象的生命周期不由它们的创建和销毁上下文决定。一旦分配，它们将持续存在，直到显式地被释放。
适用场景：适合存储需要在函数调用之间持续存在的数据，或者数据量太大无法在栈上分配的情况。
栈和堆的比较
- 存储管理：栈是自动管理的，而堆需要手动管理（在某些高级语言中，如Java和Python，有垃圾回收机制）。
- 生命周期：栈上的数据生命周期与函数调用相关，而堆上的数据生命周期更灵活。
- 性能：栈上的数据访问更快，但空间有限；堆提供更多的空间，但性能开销更大。
- 用途：栈适合于小量但快速的变量存储，堆适合于大量数据或需要跨函数持久存储的情况。
理解这些差异对于编写高效和稳定的程序至关重要。错误地使用堆和栈可能导致各种问题，如栈溢出、内存泄露或程序崩溃。
全局变量
在 C++ 中，全局变量不属于堆（Heap）也不属于栈（Stack）。全局变量以及静态变量（不管是全局的还是函数内的静态变量）被存储在一个单独的内存区域，通常称为“全局/静态存储区”或“数据段（Data Segment）”。
全局/静态存储区
生命周期：全局变量和静态变量的生命周期从程序开始执行时就开始了，直到程序结束时才销毁。
初始化：全局变量和静态变量在程序开始执行之前就已经被初始化。如果没有显式地初始化，它们会被自动初始化为零（对于基本数据类型）。
存储位置：这些变量不是存储在常规的栈或堆内存区域，而是在一个专门的内存区域，这有助于它们保持在整个程序执行过程中的持久性。
访问范围：全局变量可以在整个程序中任何位置被访问（除非它们被限制在某个特定的命名空间内）。
区别于堆和栈
与栈的区别：栈用于存储局部变量和函数调用的上下文。栈上的变量通常在函数调用结束时被销毁。
与堆的区别：堆用于动态内存分配，程序员可以控制何时分配和释放内存。堆上的变量在手动释放之前不会被销毁。
重要性
理解这些不同类型的存储区域对于编写高效和稳定的程序非常重要。错误地管理这些不同类型的内存可能导致内存泄漏、数据不一致或程序崩溃等问题。全局变量的使用应该谨慎进行，因为它们可以从程序的任何地方被访问和修改，这可能导致代码难以理解和维护。
L2-038 病毒溯源
分数 25 作者 陈越 单位 浙江大学
病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。
现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。
在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。
输入格式：
输入在第一行中给出一个正整数 N（≤10^4），即病毒种类的总数。于是我们将所有病毒从 0 到 N−1 进行编号。
随后 N 行，每行按以下格式描述一种病毒的变异情况：
k 变异株1 …… 变异株k
其中 k 是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒（0≤i<N）。题目保证病毒源头有且仅有一个。
输出格式：
首先输出从源头开始最长变异链的长度。
在第二行中输出从源头开始最长的一条变异链，编号间以 1 个空格分隔，行首尾不得有多余空格。如果最长链不唯一，则输出最小序列。
注：我们称序列 {a_1,⋯,a_n} 比序列 { b_1,⋯,b_n} “小”，如果存在 1≤k≤n 满足 a_i=b_i 对所有 i<k 成立，且 a_k<b_k。
输入样例：
10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1输出样例：
4
0 4 9 1代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 464 | 3 | 答案正确 | 12 / 12 | |
| 1 | 448 | 4 | 答案错误 | 0 / 3 | |
| 2 | 460 | 3 | 答案正确 | 1 / 1 | |
| 3 | 452 | 3 | 答案错误 | 0 / 1 | |
| 4 | 1248 | 9 | 答案错误 | 0 / 2 | |
| 5 | 2104 | 39 | 答案正确 | 4 / 4 | |
| 6 | 1344 | 8 | 答案错误 | 0 / 2 |
此时我还没有对大小进行筛选，仅完成了简单的最大深度的搜索和路径的记忆。
#include<vector>
#include<set>
#include<iostream>
using namespace std;
int maxDepth=0;
vector<int> maxPath;
void dfs(vector<set<int>>& vs,int now,int depth,vector<int>& path){
path.push_back(now);
if(depth>maxDepth){
maxDepth=depth;
maxPath=path;
}
for(auto &i:vs[now]){
dfs(vs,i,depth+1,path);
}
path.pop_back();
}
int main(){
int n;
cin>>n;
vector<set<int>> vs(n);
for(int i=0;i<n;i++){
int k,temp;
cin>>k;
while(k--){
cin>>temp;
vs[i].insert(temp);
}
}
vector<int> path;
dfs(vs,0,1,path);
cout<<maxDepth<<endl;
for(int i=0;i<maxPath.size();i++){
if(i>0) cout<<" ";
cout<<maxPath[i];
}
cout<<endl;
return 0;
}Code2
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 440 | 3 | 答案正确 | 12 / 12 | |
| 1 | 336 | 3 | 答案错误 | 0 / 3 | |
| 2 | 316 | 3 | 答案正确 | 1 / 1 | |
| 3 | 316 | 3 | 答案错误 | 0 / 1 | |
| 4 | 1336 | 8 | 答案错误 | 0 / 2 | |
| 5 | 2100 | 45 | 答案正确 | 4 / 4 | |
| 6 | 1340 | 7 | 答案错误 | 0 / 2 |
选取了值最小的路径。但是我发现0可能不是头。
#include<vector>
#include<set>
#include<iostream>
using namespace std;
int maxDepth=0;
vector<int> maxPath;
void dfs(vector<set<int>>& vs,int now,int depth,vector<int>& path){
path.push_back(now);
if(depth>maxDepth){
maxDepth=depth;
maxPath=path;
}else if(depth==maxDepth){
for(int i=0;i<maxDepth;i++){
if(maxPath[i]==path[i]){
continue;
}else if(maxPath[i]<path[i]){
break;
}else{
maxPath=path;
break;
}
}
}
for(auto &i:vs[now]){
dfs(vs,i,depth+1,path);
}
path.pop_back();
}
int main(){
int n;
cin>>n;
vector<set<int>> vs(n);
for(int i=0;i<n;i++){
int k,temp;
cin>>k;
while(k--){
cin>>temp;
vs[i].insert(temp);
}
}
vector<int> path;
dfs(vs,0,1,path);
cout<<maxDepth<<endl;
for(int i=0;i<maxPath.size();i++){
if(i>0) cout<<" ";
cout<<maxPath[i];
}
cout<<endl;
return 0;
}Code3
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 4 | 答案正确 | 12 / 12 | |
| 1 | 472 | 4 | 答案正确 | 3 / 3 | |
| 2 | 448 | 4 | 答案正确 | 1 / 1 | |
| 3 | 328 | 3 | 答案正确 | 1 / 1 | |
| 4 | 1252 | 9 | 答案正确 | 2 / 2 | |
| 5 | 2168 | 43 | 答案正确 | 4 / 4 | |
| 6 | 1356 | 8 | 答案正确 | 2 / 2 |
#include<vector>
#include<set>
#include<iostream>
using namespace std;
int maxDepth=0;
vector<int> maxPath;
void dfs(vector<set<int>>& vs,int now,int depth,vector<int>& path){
if(depth>maxDepth){
maxDepth=depth;
maxPath=path;
}else if(depth==maxDepth){
for(int i=0;i<maxDepth;i++){
if(maxPath[i]==path[i]){
continue;
}else if(maxPath[i]<path[i]){
break;
}else{
maxPath=path;
break;
}
}
}
for(auto &i:vs[now]){
path.push_back(i);
dfs(vs,i,depth+1,path);
path.pop_back();
}
}
int findhead(vector<set<int>>& vs){
bool flag=false;
int head=0;
while(!flag){
flag=true;
for(int i=0;i<vs.size();i++){
if(vs[i].find(head)!=vs[i].end()){
head=i;
flag=false;
}
}
}
return head;
}
int main(){
int n;
cin>>n;
vector<set<int>> vs(n);
for(int i=0;i<n;i++){
int k,temp;
cin>>k;
while(k--){
cin>>temp;
vs[i].insert(temp);
}
}
int head=findhead(vs);
vector<int> path(1,head);
dfs(vs,head,1,path);
cout<<maxDepth<<endl;
for(int i=0;i<maxPath.size();i++){
if(i>0) cout<<" ";
cout<<maxPath[i];
}
cout<<endl;
return 0;
}L2-039 清点代码库
分数 25 作者 陈越 单位 浙江大学
上图转自新浪微博：“阿里代码库有几亿行代码，但其中有很多功能重复的代码，比如单单快排就被重写了几百遍。请设计一个程序，能够将代码库中所有功能重复的代码找出。各位大佬有啥想法，我当时就懵了，然后就挂了。。。”
这里我们把问题简化一下：首先假设两个功能模块如果接受同样的输入，总是给出同样的输出，则它们就是功能重复的；其次我们把每个模块的输出都简化为一个整数（在 \(int\) 范围内）。于是我们可以设计一系列输入，检查所有功能模块的对应输出，从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。
输入格式：
输入在第一行中给出 \(2\) 个正整数，依次为 \(N（≤10^4）\)和 \(M（≤10^2）\)，对应功能模块的个数和系列测试输入的个数。
随后 \(N\) 行，每行给出一个功能模块的 \(M\) 个对应输出，数字间以空格分隔。
输出格式：
首先在第一行输出不同功能的个数 \(K\)。随后 \(K\) 行，每行给出具有这个功能的模块的个数，以及这个功能的对应输出。数字间以 \(1\) 个空格分隔，行首尾不得有多余空格。输出首先按模块个数非递增顺序，如果有并列，则按输出序列的递增序给出。
注：所谓数列 \({ A_1, ..., A_M }\) 比 \({ B_1, ..., B_M }\) 大，是指存在 \(1≤i<M\)，使得 \(A_1=B_1，...，A_i=B_i\) 成立，且 \(A_i+1>B_i+1\)。
输入样例：
7 3
35 28 74
-1 -1 22
28 74 35
-1 -1 22
11 66 0
35 28 74
35 28 74输出样例：
4
3 35 28 74
2 -1 -1 22
1 11 66 0
1 28 74 35代码长度限制 16 KB Java (javac) 时间限制 1500 ms 内存限制 128 MB Python (python3) 时间限制 1500 ms 内存限制 64 MB 其他编译器 时间限制 500 ms 内存限制 64 MB
Code1
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 460 | 4 | 答案正确 | 12 / 12 | |
| 1 | 460 | 4 | 答案正确 | 1 / 1 | |
| 2 | 328 | 3 | 答案正确 | 1 / 1 | |
| 3 | 460 | 3 | 答案正确 | 1 / 1 | |
| 4 | 3276 | 500 | 运行超时 | 0 / 4 | |
| 5 | 460 | 141 | 答案正确 | 3 / 3 | |
| 6 | 6716 | 500 | 运行超时 | 0 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
bool cmp(pair<int,vector<int>>& a,pair<int,vector<int>>& b){
if(a.first==b.first){
for(int i=0;i<a.second.size();i++){
if(a.second[i]!=b.second[i]){
return a.second[i]<b.second[i];
}
}
}
return a.first>b.first;
}
int main(){
int n,m;
cin>>n>>m;
vector<pair<int,vector<int>>> vpv;
while(n--){
vector<int> v;
int temp;
for(int i=0;i<m;i++){
cin>>temp;
v.push_back(temp);
}
bool finded=false;
for(auto &k:vpv){
if(k.second==v){
k.first++;
finded=true;
break;
}
}
if(!finded){
vpv.push_back(make_pair(1,v));
}
}
cout<<vpv.size()<<endl;
sort(vpv.begin(),vpv.end(),cmp);
for(auto &k:vpv){
cout<<k.first;
for(auto &j:k.second){
cout<<" "<<j;
}
cout<<endl;
}
return 0;
}Code2
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 12 / 12 | |
| 1 | 452 | 3 | 答案正确 | 1 / 1 | |
| 2 | 448 | 3 | 答案正确 | 1 / 1 | |
| 3 | 464 | 3 | 答案正确 | 1 / 1 | |
| 4 | 11512 | 238 | 答案正确 | 4 / 4 | |
| 5 | 444 | 154 | 答案正确 | 3 / 3 | |
| 6 | 13304 | 284 | 答案正确 | 3 / 3 |
这个错误信息是在尝试编译一个使用 C++ 语言编写的程序时产生的。主要的问题出现在尝试使用
std::unordered_map容器来存储以std::vector<int>作为键（key）的数据。错误信息表明编译器无法找到合适的哈希函数来处理std::vector<int>类型的键。错误的核心在于
std::unordered_map需要一个哈希函数来确定元素的存储位置。对于内置数据类型（如int,double,string等），C++ 标准库提供了默认的哈希函数。然而，对于复杂的数据结构，如std::vector<int>, 标准库并没有提供默认的哈希函数。因此，当你试图创建一个以std::vector<int>作为键的unordered_map时，编译器不知道该如何计算哈希值，导致编译错误。要解决这个问题，你可以自定义一个哈希函数。这个函数需要为
std::vector<int>类型生成一个唯一的哈希值。
后面发现map也不会超时。因为map不使用哈希表，所以不用自己搓一个哈希函数了。
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<unordered_map>
#include<functional>
using namespace std;
struct VectorHash{
size_t operator()(const std::vector<int>& v) const{
std::hash<int> hasher;
size_t seed=0;
for(int i:v){
seed^=hasher(i)+0x9e3779b9+(seed<<6)+(seed>>2);
}
return seed;
}
};
bool cmp(pair<vector<int>,int>& a,pair<vector<int>,int>& b){
if(a.second==b.second){
for(int i=0;i<a.first.size();i++){
if(a.first[i]!=b.first[i]){
return a.first[i]<b.first[i];
}
}
}
return a.second>b.second;
}
int main(){
int n,m;
cin>>n>>m;
unordered_map<vector<int>,int,VectorHash> ump;
while(n--){
vector<int> v;
int temp;
for(int i=0;i<m;i++){
cin>>temp;
v.push_back(temp);
}
if(ump.find(v)!=ump.end()){
ump[v]++;
} else{
ump[v]=1;
}
}
vector<pair<vector<int>,int>> vpv(ump.begin(),ump.end());
cout<<vpv.size()<<endl;
sort(vpv.begin(),vpv.end(),cmp);
for(auto& k:vpv){
cout<<k.second;
for(auto& j:k.first){
cout<<" "<<j;
}
cout<<endl;
}
return 0;
}L2-034 口罩发放
分数 25 作者 DAI, Longao 单位 杭州百腾教育科技有限公司
为了抗击来势汹汹的 \(COVID19\) 新型冠状病毒，全国各地均启动了各项措施控制疫情发展，其中一个重要的环节是口罩的发放。
某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。
输入格式:
输入第一行是两个正整数 \(D\) 和 \(P（1≤D,P≤30）\)，表示有 \(D\) 天的数据，市民两次获得口罩的时间至少需要间隔 \(P\) 天。
接下来 \(D\) 块数据，每块给出一天的申请信息。第 \(i\) 块数据\(（i=1,⋯,D）\)的第一行是两个整数 \(T_i\) 和 \(S_i（1≤T_i,S_i≤1000）\)，表示在第 \(i\) 天有 \(T_i\) 条申请，总共有 \(S_i\) 个口罩发放名额。随后 \(T_i\) 行，每行给出一条申请信息，格式如下：
姓名 身份证号 身体情况 提交时间
给定数据约束如下：
姓名是一个长度不超过 \(10\) 的不包含空格的非空字符串；身份证号是一个长度不超过 \(20\) 的非空字符串；身体情况是 \(0\) 或者 \(1\)，\(0\) 表示自觉良好，\(1\) 表示有相关症状；提交时间是hh:mm，为\(24\)小时时间（由 \(00:00\) 到 \(23:59\)。例如 \(09:08\)。）。注意，给定的记录的提交时间不一定有序；身份证号各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。
能发放口罩的记录要求如下：
- 身份证号 必须是 \(18\) 位的数字（可以包含前导\(0\)）；
- 同一个身份证号若在第 \(i\) 天申请成功，则接下来的 \(P\) 天不能再次申请。也就是说，若第 \(i\) 天申请成功，则等到第 \(i+P+1\) 天才能再次申请；
- 在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或 \(S_i\) 个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。
输出格式:
对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。
在输出完发放记录后，你还需要输出有合法记录的、身体状况为 \(1\) 的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。
输入样例:
4 2
5 3
A 123456789012345670 1 13:58
B 123456789012345671 0 13:58
C 12345678901234567 0 13:22
D 123456789012345672 0 03:24
C 123456789012345673 0 13:59
4 3
A 123456789012345670 1 13:58
E 123456789012345674 0 13:59
C 123456789012345673 0 13:59
F F 0 14:00
1 3
E 123456789012345674 1 13:58
1 1
A 123456789012345670 0 14:11输出样例:
D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674样例解释：
输出中，第一行到第三行是第一天的部分；第四、五行是第二天的部分；第三天没有符合要求的市民；第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB 栈限制 8192 KB
Code1
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 4 | 答案错误 | 0 / 14 | |
| 1 | 448 | 4 | 答案正确 | 3 / 3 | |
| 2 | 316 | 3 | 答案正确 | 1 / 1 | |
| 3 | 448 | 4 | 答案正确 | 1 / 1 | |
| 4 | 2068 | 73 | 答案错误 | 0 / 2 | |
| 5 | 1868 | 76 | 答案错误 | 0 / 2 | |
| 6 | 328 | 4 | 答案错误 | 0 / 2 |
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<set>
using namespace std;
struct people{
string name;
string id;
bool feelok;
int h,m;
};
bool cmp(people& a,people& b){
if(a.h==b.h)
return a.m<b.m;
return a.h<b.h;
}
int main(){
int d,p,t,s;
cin>>d>>p;
unordered_map<string,int> ump;
vector<pair<string,string>> vec;
set<string> st;
while(d--){
cin>>t>>s;
vector<string> tomove;
for(auto &k:ump){
k.second--;
if(k.second==0){
tomove.push_back(k.first);
}
}
for(auto &k:tomove){
ump.erase(k);
}
vector<people> v;
while(t--){
people peo;
cin>>peo.name>>peo.id;
cin>>peo.feelok;
scanf("%d:%d",&peo.h,&peo.m);
getchar();
if(peo.id.length()==18){
v.push_back(peo);
if(peo.feelok && st.find(peo.name)==st.end()){
st.insert(peo.name);
vec.push_back(make_pair(peo.name,peo.id));
}
}
}
sort(v.begin(),v.end(),cmp);
int cnt=0;
while(s && cnt<v.size()){
if(ump.find(v[cnt].name)==ump.end()){
ump[v[cnt].name]=p;
cout<<v[cnt].name<<" "<<v[cnt].id<<endl;
s--;
}
cnt++;
}
}
for(auto &i:vec){
cout<<i.first<<" "<<i.second<<endl;
}
return 0;
}Code2
240129
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 14 / 14 | |
| 1 | 456 | 3 | 答案错误 | 0 / 3 | |
| 2 | 444 | 4 | 答案正确 | 1 / 1 | |
| 3 | 452 | 3 | 答案正确 | 1 / 1 | |
| 4 | 2172 | 76 | 答案错误 | 0 / 2 | |
| 5 | 1964 | 71 | 答案错误 | 0 / 2 | |
| 6 | 456 | 4 | 答案错误 | 0 / 2 |
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<set>
using namespace std;
struct people{
string name;
string id;
bool feelok;
int h,m;
};
bool cmp(people& a,people& b){
if(a.h==b.h)
return a.m<b.m;
return a.h<b.h;
}
int main(){
int d,p,t,s;
cin>>d>>p;
unordered_map<string,int> ump;
vector<pair<string,string>> vec;
set<string> st;
while(d--){
cin>>t>>s;
vector<string> tomove;
for(auto &k:ump){
k.second--;
if(k.second==0){
tomove.push_back(k.first);
}
}
for(auto &k:tomove){
ump.erase(k);
}
vector<people> v;
while(t--){
people peo;
cin>>peo.name>>peo.id;
cin>>peo.feelok;
scanf("%d:%d",&peo.h,&peo.m);
getchar();
if(peo.id.length()==18){
v.push_back(peo);
if(peo.feelok && st.find(peo.name)==st.end()){
st.insert(peo.name);
vec.push_back(make_pair(peo.name,peo.id));
}
}
}
sort(v.begin(),v.end(),cmp);
// int cnt=0;
// while(s && cnt<v.size()){
// if(ump.find(v[cnt].name)==ump.end()){
// ump[v[cnt].name]=p;
// cout<<v[cnt].name<<" "<<v[cnt].id<<endl;
// s--;
// }
// cnt++;
// }
for(auto &k:v){
if(ump.find(k.name)==ump.end()){
ump[k.name]=p+1;
cout<<k.name<<" "<<k.id<<endl;
s--;
}
if(s==0){
break;
}
}
}
for(auto &i:vec){
cout<<i.first<<" "<<i.second<<endl;
}
return 0;
}Code3
240131
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 444 | 3 | 答案正确 | 14 / 14 | |
| 1 | 452 | 3 | 答案正确 | 3 / 3 | |
| 2 | 324 | 3 | 答案正确 | 1 / 1 | |
| 3 | 460 | 3 | 答案正确 | 1 / 1 | |
| 4 | 1808 | 84 | 答案正确 | 2 / 2 | |
| 5 | 1724 | 82 | 答案正确 | 2 / 2 | |
| 6 | 448 | 3 | 答案正确 | 2 / 2 |
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cctype>
using namespace std;
class people{
public:
string name;
string id;
bool feelbad;
int h,m;
int pos;
};
bool checkid(string str){
if(str.length()!=18)
return false;
for(auto &k:str){
if(!isdigit(k))
return false;
}
return true;
}
int main(){
int d,p,t,s;
cin>>d>>p;
map<string,int> mp; //领取口罩的人，倒计时
vector<people> whofeelbad;
set<string> st; //已经在whofeelbad里了
while(d--){
cin>>t>>s;
vector<string> tomove;
for(auto &k:mp){
k.second--;
if(k.second==0){
tomove.push_back(k.first);
}
}
for(auto &k:tomove){
mp.erase(k);
}
vector<people> today;
for(int i=0;i<t;i++){
people peo;
cin>>peo.name>>peo.id;
cin>>peo.feelbad;
peo.pos=i;
scanf("%d:%d",&peo.h,&peo.m);
getchar(); //有没有都没关系
if(checkid(peo.id)){
today.push_back(peo);
if(peo.feelbad && st.find(peo.name)==st.end()){
whofeelbad.push_back(peo);
st.insert(peo.name);
}
}
}
sort(today.begin(),today.end(),[&](people a,people b){
if(a.h!=b.h)
return a.h<b.h;
if(a.m!=b.m)
return a.m<b.m;
return a.pos<b.pos;
});
for(int j=0,cnt=0;j<today.size()&&cnt<s;j++){
if(!mp[today[j].name]){
mp[today[j].name]=p+1;
cout<<today[j].name<<" "<<today[j].id<<endl;
s--;
}
}
}
for(auto &k:whofeelbad){
cout<<k.name<<" "<<k.id<<endl;
}
return 0;
}L2-041 插松枝
分数 25 作者 陈越 单位 浙江大学
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：
- 每人手边有一只小盒子，初始状态为空。
- 每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
- 工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
- 工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
- 当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
- （1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
- （2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
- （3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
现在给定推送器上顺序传过来的 \(N\) 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。
输入格式：
输入在第一行中给出 \(3\) 个正整数：\(N（≤10^3）\)，为推送器上松针片的数量；\(M（≤20）\)为小盒子能存放的松针片的最大数量；\(K（≤5）\)为一根松枝干上能插的松针片的最大数量。
随后一行给出 \(N\) 个不超过 \(100\) 的正整数，为推送器上顺序推出的松针片的大小。
输出格式：
每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 \(1\) 个空格分隔，行首尾不得有多余空格。
输入样例：
8 3 4
20 25 15 18 20 18 8 5输出样例：
20 15
20 18 18 8
25 5代码长度限制 16 KB Java (javac) 时间限制 500 ms 内存限制 64 MB 其他编译器 时间限制 400 ms 内存限制 64 MB 栈限制 8192 KB
Code1
240131
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 12 / 12 | |
| 1 | 448 | 3 | 答案正确 | 3 / 3 | |
| 2 | 324 | 3 | 答案正确 | 1 / 1 | |
| 3 | 448 | 4 | 答案正确 | 3 / 3 | |
| 4 | 324 | 3 | 答案正确 | 3 / 3 | |
| 5 | 476 | 3 | 答案正确 | 3 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<stack>
#include<queue>
using namespace std;
void print(queue<int>& q){
cout<<q.front();
q.pop();
while(!q.empty()){
cout<<" "<<q.front();
q.pop();
}
cout<<endl;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
queue<int> src;
queue<int> pine;
stack<int> box;
while(n--){
int temp;
cin>>temp;
src.push(temp);
}
while(!src.empty()){
if(pine.size()==0){ //pine上没有松枝
if(box.size()==0){ //box里没有松枝
pine.push(src.front());
src.pop();
}else{ //box里有松枝
pine.push(box.top());
box.pop();
}
}else if(pine.size()>=k){ //pine满了
print(pine);
}else{ //pine上有松枝，且可以插松枝
if(box.size()==0){ //box里没有松枝
if(pine.back()>=src.front()){
pine.push(src.front());
src.pop();
}else{
box.push(src.front());
src.pop();
}
}else if(box.size()>=m){ //box满了
if(pine.back()>=src.front()){
pine.push(src.front());
src.pop();
}else{
print(pine);
}
}else{ //box里有空位
if(pine.back()>=box.top()){
pine.push(box.top());
box.pop();
}else{
if(pine.back()>=src.front()){
pine.push(src.front());
src.pop();
}else{
box.push(src.front());
src.pop();
}
}
}
}
}
while(!box.empty()){
if(pine.size()==0){
pine.push(box.top());
box.pop();
}else if(pine.size()>=k){
print(pine);
}else if(box.top()>=pine.back()){
print(pine);
}else{
pine.push(box.top());
box.pop();
}
}
while(!pine.empty()){
print(pine);
}
return 0;
}L2-042 老板的作息表
分数 25 作者 陈越 单位 浙江大学
新浪微博上有人发了某老板的作息时间表，表示其每天 \(4:30\) 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？
本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。
输入格式：
输入第一行给出一个正整数 \(N\)，为作息表上列出的时间段的个数。随后
\(N\) 行，每行给出一个时间段，格式为：
hh:mm:ss - hh:mm:ss
输出格式：
按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。
输入样例：
8
13:00:00 - 18:00:00
00:00:00 - 01:00:05
08:00:00 - 09:00:00
07:10:59 - 08:00:00
01:00:05 - 04:30:00
06:30:00 - 07:10:58
05:30:00 - 06:30:00
18:00:00 - 19:00:00输出样例：
04:30:00 - 05:30:00
07:10:58 - 07:10:59
09:00:00 - 13:00:00
19:00:00 - 23:59:59代码长度限制 16 KB Java (javac) 时间限制 900 ms 内存限制 128 MB Python (python3) 时间限制 300 ms 内存限制 64 MB 其他编译器 时间限制 200 ms 内存限制 64 MB 栈限制 8192 KB
Code
240131
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 432 | 3 | 答案正确 | 13 / 13 | |
| 1 | 448 | 3 | 答案正确 | 2 / 2 | |
| 2 | 448 | 3 | 答案正确 | 2 / 2 | |
| 3 | 1208 | 28 | 答案正确 | 4 / 4 | |
| 4 | 1212 | 28 | 答案正确 | 4 / 4 |
第\(17\)行必须要加cur!=3600*24-1，否则出现下面的输入输出错误：
Input:
1
00:00:00 - 23:59:59
Output:
23:59:59 - 23:59:59#include<iostream>
#include<vector>
using namespace std;
vector<bool> times;
int main(){
times.resize(3600*24,true);
int n;cin>>n;
while(n--){
int h1,m1,s1,h2,m2,s2;
scanf("%d:%d:%d - %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);
for(int i=h1*3600+m1*60+s1;i<h2*3600+m2*60+s2;i++){
times[i]=false;
}
}
int cur=0;
while(cur<3600*24){
if(times[cur] && cur!=3600*24-1){
int begin=cur;
while(times[cur++] && cur<3600*24);
cur--;
printf("%02d:%02d:%02d - %02d:%02d:%02d\n",begin/3600,begin/60%60,begin%60,cur/3600,cur/60%60,cur%60);
}
cur++;
}
return 0;
}L2-043 龙龙送外卖
分数 25 作者 DAI, Longao 单位 杭州百腾教育科技有限公司
龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。
每到中午 \(12\) 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……
看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。
输入格式:
输入第一行是两个数 \(N\) 和 \(M (2≤N≤10^5, 1≤M≤10^5)\)，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。
接下来首先是一行 \(N\) 个数，第 \(i\) 个数表示第 \(i\) 个点的双亲节点的编号。节点编号从 \(1\) 到 \(N\)，外卖站的双亲编号定义为 \(−1\)。
接下来有 \(M\) 行，每行给出一个新增的送餐地点的编号 $X_i4 。保证送餐地点中不会有外卖站，但地点有可能会重复。
为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 \(1\)，且从外卖站出发可以访问到所有地点。
注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。
输出格式:
对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。
输入样例:
7 4
-1 1 1 1 2 2 3
5
6
2
4输出样例:
2
4
4
6代码长度限制 16 KB Java (javac) 时间限制 1400 ms 内存限制 256 MB Python (python3) 时间限制 600 ms 内存限制 64 MB 其他编译器 时间限制 400 ms 内存限制 64 MB 栈限制 131072 KB
Code1
240202
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 440 | 3 | 答案错误 | 0 / 12 | |
| 1 | 444 | 3 | 答案错误 | 0 / 1 | |
| 2 | 444 | 3 | 答案错误 | 0 / 1 | |
| 3 | 324 | 2 | 答案正确 | 1 / 1 | |
| 4 | 65536 | 120 | 内存超限 | 0 / 2 | |
| 5 | 65536 | 118 | 内存超限 | 0 / 3 | |
| 6 | 65536 | 117 | 内存超限 | 0 / 2 | |
| 7 | 1076 | 400 | 运行超时 | 0 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
int n,m;
vector<int> route;
int main(){
cin>>n>>m;
route.resize(n+1);
for(int i=1;i<=n;i++){
cin>>route[i];
}
vector<int> lastpath;
vector<int> currentpath;
int point,dist=0,i=0;
cin>>point;
while(point!=1){
lastpath.push_back(point);
point=route[point];
}
reverse(lastpath.begin(),lastpath.end());
dist+=lastpath.size();
cout<<dist<<endl;
for(int j=0;j<m-1;j++){
cin>>point;
while(point!=1){
currentpath.push_back(point);
point=route[point];
}
reverse(currentpath.begin(),currentpath.end());
for(i=0;i<min(lastpath.size(),currentpath.size());i++){
if(currentpath[i]!=lastpath[i]) break;
}
dist+=(currentpath.size()-i)*2;
lastpath=currentpath;
currentpath.resize(0);
cout<<dist<<endl;
}
return 0;
}Code2
240202
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 3 | 答案正确 | 12 / 12 | |
| 1 | 65536 | 52 | 内存超限 | 0 / 1 | |
| 2 | 472 | 3 | 答案正确 | 1 / 1 | |
| 3 | 472 | 3 | 答案正确 | 1 / 1 | |
| 4 | 65536 | 73 | 内存超限 | 0 / 2 | |
| 5 | 65536 | 72 | 内存超限 | 0 / 3 | |
| 6 | 65536 | 70 | 内存超限 | 0 / 2 | |
| 7 | 6452 | 241 | 答案正确 | 3 / 3 |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n,m;
vector<int> route;
vector<int> depth;
set<int> used;
int dfs(int n){
if(n==1) return 0;
if(depth[route[n]]) return depth[route[n]]+1;
depth[route[n]]=dfs(route[n]);
return depth[route[n]]+1;
}
int main(){
cin>>n>>m;
route.resize(n+1);
depth.resize(n+1,0);
for(int i=1;i<=n;i++){
cin>>route[i];
}
for(int i=2;i<=n;i++){
depth[i]=dfs(i);
}
int temp,mx=0,sum=0;
used.insert(1);
while(m--){
cin>>temp;
if(used.find(temp)==used.end()){
mx=(depth[temp]>mx)?depth[temp]:mx;
int add=0;
while(used.find(temp)==used.end()){
used.insert(temp);
add++;
temp=route[temp];
}
sum+=add*2;
}
cout<<sum-mx<<endl;
}
return 0;
}Code3
240202
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 4276 | 5 | 答案正确 | 12 / 12 | |
| 1 | 4328 | 5 | 答案正确 | 1 / 1 | |
| 2 | 4288 | 5 | 答案正确 | 1 / 1 | |
| 3 | 4364 | 5 | 答案正确 | 1 / 1 | |
| 4 | 7996 | 165 | 答案正确 | 2 / 2 | |
| 5 | 6456 | 168 | 答案正确 | 3 / 3 | |
| 6 | 6448 | 160 | 答案正确 | 2 / 2 | |
| 7 | 6456 | 161 | 答案正确 | 3 / 3 |
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=10e5+10;
int n,m,sum=0;
int route[M];
int depth[M];
int dfs(int x){
if(route[x]==-1) return 0;
sum++;
if(depth[route[x]]==-1){
depth[route[x]]=dfs(route[x]);
}
return depth[route[x]]+1;
}
int main(){
cin>>n>>m;
memset(depth,-1,sizeof(depth));
for(int i=1;i<=n;i++){
cin>>route[i];
}
int mx=0;
while(m--){
int temp;
cin>>temp;
if(depth[temp]==-1){
depth[temp]=dfs(temp);
}
mx=max(mx,depth[temp]);
cout<<sum*2-mx<<endl;
}
return 0;
}L3-001 凑零钱
分数 30 作者 陈越 单位 浙江大学
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 \(10^4\) 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
输入格式：
输入第一行给出两个正整数：\(N（≤10^4）\)是硬币的总个数，\(M（≤10^2）\)是韩梅梅要付的款额。第二行给出 \(N\) 枚硬币的正整数面值。数字间以空格分隔。
输出格式：
在一行中输出硬币的面值 \(V_1≤V_2≤⋯≤V_k\)，满足条件 \(V_1+V_2+...+V_k=M\)。数字间以 \(1\)
个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出
No Solution。
注：我们说序列\({ A[1],A[2],⋯ }\)比\({ B[1],B[2],⋯ }\)“小”，是指存在 \(k≥1\) 使得 \(A[i]=B[i]\) 对所有 \(i<k\) 成立，并且 \(A[k]<B[k]\)。
输入样例 1：
8 9
5 9 8 7 2 3 4 1输出样例 1：
1 3 5输入样例 2：
4 8
7 2 4 3输出样例 2：
No Solution代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB
Code
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 464 | 3 | 答案正确 | 16 / 16 | |
| 1 | 448 | 3 | 答案正确 | 1 / 1 | |
| 2 | 452 | 3 | 答案正确 | 5 / 5 | |
| 3 | 472 | 10 | 答案正确 | 2 / 2 | |
| 4 | 436 | 14 | 答案正确 | 4 / 4 | |
| 5 | 320 | 2 | 答案正确 | 1 / 1 | |
| 6 | 452 | 5 | 答案正确 | 1 / 1 |
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e2+10;
bool cmp(vector<int>& a,vector<int>& b){
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int min_size=min(a.size(),b.size());
for(int i=0;i<min_size;i++){
if(a[i]<b[i]){
return true; // Choose front one
}else if(a[i]>b[i]){
return false; // Choose back one
}
}
return true;
}
int main(){
int n,m;
cin>>n>>m;
vector<int> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
sort(v.begin(),v.end(),[&](int a,int b){
return a>b;
});
// for(auto &k:v){
// cout<<" "<<k;
// }cout<<endl;
vector<vector<int>> pre(m+1);
vector<vector<int>> now(m+1);
for(int j=0;j<=m;j++){
if(j==v[0]) pre[j].push_back(v[0]);
}
for(int i=1;i<n;i++){
// cout<<"i = "<<i<<endl;
for(int j=0;j<=m;j++){
if(j<v[i]){
now[j]=pre[j];
}else if(j==v[i]){
if(pre[j].size()!=0){
now[j]=pre[j];
}else{
now[j].push_back(v[i]);
}
}else
{
if(pre[j-v[i]].size()==0){
now[j]=pre[j];
}else{
vector<int> temp=pre[j-v[i]];
temp.push_back(v[i]);
if(cmp(temp,pre[j])){
now[j]=temp;
}else{
now[j]=pre[j];
}
}
}
// if(pre[j].size()==0 && v[i]==j){
// now[j]=pre[j-v[i]];
// now[j].push_back(v[i]);
// }else if(pre[j].size()!=0 && pre[j-v[i]].size()!=0){
// vector<int> temp=pre[j-v[i]];
// temp.push_back(v[i]);
// if(cmp(temp,pre[j])){
// now[j]=temp;
// }else{
// now[j]=pre[j];
// }
// }else{
// cout<<"Unkown Error"<<endl;
// }
//
// cout<<"j="<<j<<" |";
// for(auto &k:now[j]){
// cout<<" "<<k;
// }cout<<endl;
}
// cout<<endl;
swap(pre,now);
}
if(pre[m].size()>0){
for(int i=0;i<pre[m].size();i++){
if(i) cout<<" ";
cout<<pre[m][i];
}
cout<<endl;
}else{
cout<<"No Solution"<<endl;
}
return 0;
}L3-002 特殊堆栈
分数 30 作者 陈越 单位 浙江大学
堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 \(N\) 个元素，如果 \(N\) 是偶数，则中值定义为第 \(N/2\) 小元；若是奇数，则为第 \((N+1)/2\) 小元。
输入格式：
输入的第一行是正整数 \(N（≤10^5）\)。随后 \(N\) 行，每行给出一句指令，为以下 \(3\) 种之一：
Push key
Pop
PeekMedian其中 key 是不超过 \(10^5\) 的正整数；Push
表示“入栈”；Pop 表示“出栈”；PeekMedian
表示“取中值”。
输出格式：
对每个 Push 操作，将 key
插入堆栈，无需输出；对每个 Pop 或 PeekMedian
操作，在一行中输出相应的返回值。若操作非法，则对应输出
Invalid。
输入样例：
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop输出样例：
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
Code1
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 460 | 3 | 答案正确 | 15 / 15 | |
| 1 | 496 | 400 | 运行超时 | 0 / 5 | |
| 2 | 608 | 400 | 运行超时 | 0 / 5 | |
| 3 | 564 | 400 | 运行超时 | 0 / 3 | |
| 4 | 464 | 3 | 答案正确 | 2 / 2 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int c;
cin>>c;
string op;
int num;
vector<int> v;
while(c--){
cin>>op;
if(op=="Pop" && !v.empty()){
cout<<v.back()<<endl;
v.pop_back();
}else if(op=="Push"){
cin>>num;
v.push_back(num);
}else if(op=="PeekMedian" && !v.empty()){
vector<int> temp=v;
sort(temp.begin(),temp.end());
cout<<temp[(temp.size()-1)/2]<<endl;
}else{
cout<<"Invalid"<<endl;
}
}
return 0;
}From CSDN
思路：此处是的难点在与查询区间的中第n/2大的数， 且该区间还要实现删除和增加新元素， 大致有这四种方法实现
构建两个堆，形成双顶堆， 其中顶堆中的数都大于底堆中的数,且底堆中的size永远比顶堆的size大1；
第二种方法，用树状数组加二分查找第n/2大即可
第三种就是用vetor插入，每次插入时二分区间找到该插入的位置insert， 删除时也同样二分并erase(), 查询mid时直接输出即可效率较高。此处的二分查询可以直接用low_bound
第四种便是用线段树查询区间第k打也很简单，
Code2
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 15 / 15 | |
| 1 | 1124 | 110 | 答案正确 | 5 / 5 | |
| 2 | 1188 | 191 | 答案正确 | 5 / 5 | |
| 3 | 1252 | 153 | 答案正确 | 3 / 3 | |
| 4 | 460 | 3 | 答案正确 | 2 / 2 |
#include<bits/stdc++.h>
using namespace std;
int main(){
int c;
cin>>c;
string op;
int num;
vector<int> v;
vector<int> v_sort;
while(c--){
cin>>op;
if(op=="Pop" && !v.empty()){
cout<<v.back()<<endl;
auto cur=lower_bound(v_sort.begin(),v_sort.end(),v.back());
v_sort.erase(cur);
v.pop_back();
}else if(op=="Push"){
cin>>num;
v.push_back(num);
auto cur=lower_bound(v_sort.begin(),v_sort.end(),num);
v_sort.insert(cur,num);
}else if(op=="PeekMedian" && !v.empty()){
cout<<v_sort[(v_sort.size()-1)/2]<<endl;
}else{
cout<<"Invalid"<<endl;
}
}
return 0;
}L3-003 社交集群
分数 30 作者 陈越 单位 浙江大学
当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。
输入格式：
输入在第一行给出一个正整数 \(N（≤1000）\)，为社交网络平台注册的所有用户的人数。于是这些人从 \(1\) 到 \(N\) 编号。随后 \(N\) 行，每行按以下格式给出一个人的兴趣爱好列表：
\(K_i: h_i[1] h_i[2] ... h_i[K_i]\) 其中 \(K_i(>0)\) 是兴趣爱好的个数，\(h_i[j]\)是第\(j\)个兴趣爱好的编号，为区间 \([1, 1000]\) 内的整数。
输出格式：
首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。
输入样例：
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4输出样例：
3
4 3 1代码长度限制 16 KB 时间限制 1200 ms 内存限制 64 MB
Code
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 444 | 3 | 答案正确 | 16 / 16 | |
| 1 | 444 | 3 | 答案错误 | 0 / 4 | |
| 2 | 452 | 3 | 答案错误 | 0 / 1 | |
| 3 | 316 | 3 | 答案正确 | 3 / 3 | |
| 4 | 452 | 3 | 答案错误 | 0 / 3 | |
| 5 | 452 | 4 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
vector<int> roots;
vector<int> people;
int findroot(int n){
if(roots[n]==n) return n;
else{
roots[n]=findroot(roots[n]);
return roots[n];
}
}
int main(){
int n;
cin>>n;
roots.resize(M);
people.resize(M,0);
set<int> s;
for(int i=0;i<M;i++){
roots[i]=i;
}
for(int i=0;i<n;i++){
int c;
char colon;
cin>>c>>colon;
vector<int> tmp(c);
for(int j=0;j<c;j++){
cin>>tmp[j];
s.insert(tmp[j]);
}
int root=findroot(tmp[0]);
people[root]++;
for(int j=1;j<c;j++){
roots[findroot(tmp[j])]=root;
people[root]+=people[tmp[j]];
people[tmp[j]]=0;
}
// cout<<"roots:";
// for(int i=0;i<=10;i++){
// cout<<" "<<roots[i];
// }
// cout<<endl<<"peopl:";
// for(int i=0;i<=10;i++){
// cout<<" "<<people[i];
// }
// cout<<endl;
}
// map<int,int> m;
// for(auto &k:s){
// if(!m[findroot(k)]){
// m[findroot(k)]=1;
// }else{
// m[findroot(k)]++;
// }
// }
// vector<pair<int,int>> res(m.begin(),m.end());
// sort(res.begin(),res.end(),[&](pair<int,int>a,pair<int,int>b){
// return a.second>b.second;
// });
// for(auto &k:res){
// cout<<" "<<k.second;
// }
sort(people.begin(),people.end(),[&](int a,int b){return a>b;});
auto cur=people.begin();
while(*(cur)!=0) cur++;
vector<int> res(people.begin(),cur);
cout<<res.size()<<endl;
for(int i=0;i<M;i++){
if(res[i]==0) break;
if(i) cout<<" ";
cout<<res[i];
}
return 0;
}Code2
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 16 / 16 | |
| 1 | 444 | 3 | 答案正确 | 4 / 4 | |
| 2 | 548 | 4 | 答案错误 | 0 / 1 | |
| 3 | 440 | 3 | 答案正确 | 3 / 3 | |
| 4 | 468 | 4 | 答案正确 | 3 / 3 | |
| 5 | 444 | 4 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
vector<int> roots;
vector<int> people;
int findroot(int n){
if(roots[n]==n) return n;
else{
roots[n]=findroot(roots[n]);
return roots[n];
}
}
int main(){
int n;
cin>>n;
roots.resize(M);
people.resize(M,0);
set<int> s;
for(int i=0;i<M;i++){
roots[i]=i;
}
for(int i=0;i<n;i++){
int c;
char colon;
cin>>c>>colon;
vector<int> tmp(c);
for(int j=0;j<c;j++){
cin>>tmp[j];
s.insert(tmp[j]);
}
int root=findroot(tmp[0]);
people[root]++;
for(int j=1;j<c;j++){
people[root]+=people[findroot(tmp[j])];
people[findroot(tmp[j])]=0;
roots[findroot(tmp[j])]=root;
}
// cout<<"roots:";
// for(int i=0;i<=10;i++){
// cout<<" "<<roots[i];
// }
// cout<<endl<<"peopl:";
// for(int i=0;i<=10;i++){
// cout<<" "<<people[i];
// }
// cout<<endl;
}
sort(people.begin(),people.end(),[&](int a,int b){return a>b;});
auto cur=people.begin();
while(*(cur)!=0) cur++;
vector<int> res(people.begin(),cur);
cout<<res.size()<<endl;
for(int i=0;i<M;i++){
if(res[i]==0) break;
if(i) cout<<" ";
cout<<res[i];
}
cout<<endl;
return 0;
}Code3
240205
修了几个逻辑错误还是差一个测试点
修复了第37行输入如下数据时的错误。 2
2: 1 2
2: 1 2
修复了输入0时的段错误。
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
vector<int> roots;
vector<int> people;
int findroot(int n){
if(roots[n]==n) return n;
else{
roots[n]=findroot(roots[n]);
return roots[n];
}
}
int main(){
int n;
cin>>n;
roots.resize(M);
people.resize(M,0);
set<int> s;
for(int i=0;i<M;i++){
roots[i]=i;
}
for(int i=0;i<n;i++){
int c;
char colon;
cin>>c>>colon;
vector<int> tmp(c);
for(int j=0;j<c;j++){
cin>>tmp[j];
s.insert(tmp[j]);
}
int root=findroot(tmp[0]);
people[root]++;
for(int j=1;j<c;j++){
int temp=people[findroot(tmp[j])];
people[findroot(tmp[j])]=0;
people[root]+=temp;
roots[findroot(tmp[j])]=root;
}
// cout<<"roots:";
// for(int i=0;i<=10;i++){
// cout<<" "<<roots[i];
// }
// cout<<endl<<"peopl:";
// for(int i=0;i<=10;i++){
// cout<<" "<<people[i];
// }
// cout<<endl;
}
if(n){
sort(people.begin(),people.end(),[&](int a,int b){return a>b;});
auto cur=people.begin();
while(*(cur)!=0) cur++;
vector<int> res(people.begin(),cur);
cout<<res.size()<<endl;
for(int i=0;i<M;i++){
if(res[i]==0) break;
if(i) cout<<" ";
cout<<res[i];
}
cout<<endl;
}else{
cout<<0<<endl;
}
return 0;
}Code3
240205
改成set就对了？？？我也不知道为什么
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 440 | 3 | 答案正确 | 16 / 16 | |
| 1 | 444 | 5 | 答案正确 | 4 / 4 | |
| 2 | 436 | 3 | 答案正确 | 1 / 1 | |
| 3 | 320 | 3 | 答案正确 | 3 / 3 | |
| 4 | 444 | 3 | 答案正确 | 3 / 3 | |
| 5 | 484 | 3 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
vector<int> roots;
vector<int> people;
int findroot(int n){
if(roots[n]!=n)
roots[n]=findroot(roots[n]);
return roots[n];
}
int main(){
int n;
cin>>n;
roots.resize(M);
people.resize(M,0);
set<int> s;
for(int i=0;i<M;i++){
roots[i]=i;
}
for(int i=0;i<n;i++){
int c,temp,root;
char colon;
cin>>c>>colon>>root;
s.clear();
root=findroot(root);
people[root]++;
c--;
while(c--){
cin>>temp;
s.insert(temp);
}
for(auto &k:s){
if(people[findroot(k)] && findroot(k)!=root){
people[root]+=people[findroot(k)];
people[findroot(k)]=0;
}
roots[findroot(k)]=root;
}
// // Debug
// cout<<"roots:";
// for(int i=0;i<=10;i++) cout<<" "<<roots[i];
// cout<<endl<<"peopl:";
// for(int i=0;i<=10;i++) cout<<" "<<people[i];
// cout<<endl;
}
sort(people.begin(),people.end(),[&](int a,int b){return a>b;});
auto cur=people.begin();
while(*(cur)!=0) cur++;
vector<int> res(people.begin(),cur);
cout<<res.size()<<endl;
for(int i=0;i<M;i++){
if(res[i]==0) break;
if(i) cout<<" ";
cout<<res[i];
}
cout<<endl;
return 0;
}L3-004 肿瘤诊断
分数 30 作者 陈越 单位 浙江大学
在诊断肿瘤疾病时，计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域，请你计算肿瘤的体积。
输入格式：
输入第一行给出\(4\)个正整数：\(M、N、L、T\)，其中\(M\)和\(N\)是每张切片的尺寸（即每张切片是一个\(M×N\)的像素矩阵。最大分辨率是\(1286×128\)）；\(L（≤60）\)是切片的张数；\(T\)是一个整数阈值（若疑似肿瘤的连通体体积小于T，则该小块忽略不计）。
最后给出\(L\)张切片。每张用一个由\(0\)和\(1\)组成的\(M×N\)的矩阵表示，其中\(1\)表示疑似肿瘤的像素，\(0\)表示正常像素。由于切片厚度可以认为是一个常数，于是我们只要数连通体中\(1\)的个数就可以得到体积了。麻烦的是，可能存在多个肿瘤，这时我们只统计那些体积不小于T的。两个像素被认为是“连通的”，如果它们有一个共同的切面，如下图所示，所有\(6\)个红色的像素都与蓝色的像素连通。
输出格式：
在一行中输出肿瘤的总体积。
输入样例：
3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0输出样例：
26代码长度限制 16 KB 时间限制 600 ms 内存限制 64 MB
Code
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 11072 | 9 | 答案正确 | 15 / 15 | |
| 1 | 11204 | 10 | 答案正确 | 6 / 6 | |
| 2 | 11136 | 10 | 答案正确 | 2 / 2 | |
| 3 | 11076 | 9 | 答案正确 | 2 / 2 | |
| 4 | 15416 | 101 | 答案正确 | 2 / 2 | |
| 5 | 15424 | 96 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
const int M=1300,N=130,L=65;
int m,n,l,t;
int matrix[L][M][N];
bool used[L][M][N];
int dir1[]={0,0,0,0,1,-1};
int dir2[]={0,0,1,-1,0,0};
int dir3[]={1,-1,0,0,0,0};
struct coor{ // 坐标coordinate
int z,y,x;
};
int bfs(int i,int j,int k){
int volume=0,t1,t2,t3;
queue<coor> q;
coor co;
co.x=k;
co.y=j;
co.z=i;
q.push(co);
used[i][j][k]=true;
while(!q.empty()){
coor now=q.front();
q.pop();
volume++;
for(int o=0;o<6;o++){
t1=now.z+dir1[o];
t2=now.y+dir2[o];
t3=now.x+dir3[o];
if(t1>=0 && t1<l && t2>=0 && t2<m && t3>=0 && t3<n && matrix[t1][t2][t3] && !used[t1][t2][t3]){
co.x=t3,co.y=t2,co.z=t1;
q.push(co);
used[t1][t2][t3]=true;
matrix[t1][t2][t3]=0;
}
}
}
return volume;
}
void print(){
for(int i=0;i<l;i++){
for(int j=0;j<m;j++){
for(int k=0;k<n;k++){
printf("%d",matrix[i][j][k]);
}
printf("\n");
}
printf("\n");
}
printf("\n");
}
int main(){
memset(used,false,sizeof(used));
scanf("%d%d%d%d",&m,&n,&l,&t);
for(int i=0;i<l;i++)
for(int j=0;j<m;j++)
for(int k=0;k<n;k++){
scanf("%d",&matrix[i][j][k]);
}
int res=0;
for(int i=0;i<l;i++){
for(int j=0;j<m;j++){
for(int k=0;k<n;k++){
if(matrix[i][j][k] && !used[i][j][k]){
int temp=bfs(i,j,k);
if(temp>=t) res+=temp;
// cout<<temp<<endl;
// print();
}
}
}
}
printf("%d\n",res);
return 0;
}Code2
优化
240205
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 448 | 3 | 答案正确 | 15 / 15 | |
| 1 | 440 | 4 | 答案正确 | 6 / 6 | |
| 2 | 460 | 3 | 答案正确 | 2 / 2 | |
| 3 | 452 | 3 | 答案正确 | 2 / 2 | |
| 4 | 4672 | 91 | 答案正确 | 2 / 2 | |
| 5 | 4532 | 104 | 答案正确 | 3 / 3 |
#include<bits/stdc++.h>
using namespace std;
const int M=1300,N=130,L=65;
int m,n,l,t;
int matrix[L][M][N];
int dir1[]={0,0,0,0,1,-1};
int dir2[]={0,0,1,-1,0,0};
int dir3[]={1,-1,0,0,0,0};
struct coor{ // 坐标coordinate
int z,y,x;
};
int bfs(int i,int j,int k){
int volume=0,t1,t2,t3;
queue<coor> q;
q.push(coor{i,j,k});
matrix[i][j][k]=0;
while(!q.empty()){
coor now=q.front();
q.pop();
volume++;
for(int o=0;o<6;o++){
t1=now.z+dir1[o];
t2=now.y+dir2[o];
t3=now.x+dir3[o];
if(t1>=0 && t1<l && t2>=0 && t2<m && t3>=0 && t3<n && matrix[t1][t2][t3]){
q.push(coor{t1,t2,t3});
matrix[t1][t2][t3]=0;
}
}
}
return volume;
}
int main(){
scanf("%d%d%d%d",&m,&n,&l,&t);
for(int i=0;i<l;i++)
for(int j=0;j<m;j++)
for(int k=0;k<n;k++){
scanf("%d",&matrix[i][j][k]);
}
int res=0;
for(int i=0;i<l;i++){
for(int j=0;j<m;j++){
for(int k=0;k<n;k++){
if(matrix[i][j][k]){
int temp=bfs(i,j,k);
if(temp>=t) res+=temp;
}
}
}
}
printf("%d\n",res);
return 0;
}L3-005 垃圾箱分布
分数 30 作者 陈越 单位 浙江大学
大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。
现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。
输入格式：
输入第一行给出\(4\)个正整数：\(N（≤10^3）\)是居民点的个数；\(M（≤10）\)是垃圾箱候选地点的个数；\(K（≤10^4）\)是居民点和垃圾箱候选地点之间的道路的条数；\(D_S\)是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从\(1\)到\(N\)编号，所有的垃圾箱候选地点从\(G1\)到\(GM\)编号。
随后K行，每行按下列格式描述一条道路：
P1 P2 Dist 其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。
输出格式：
首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出No Solution。
输入样例1：
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2输出样例1：
G1
2.0 3.3输入样例2：
2 1 2 10
1 G1 9
2 G1 20输出样例2：
No Solution代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB
Code1
240206
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 444 | 3 | 答案正确 | 16 / 16 | |
| 1 | 324 | 2 | 答案正确 | 2 / 2 | |
| 2 | 456 | 3 | 答案正确 | 4 / 4 | |
| 3 | 384 | 3 | 答案正确 | 4 / 4 | |
| 4 | 316 | 3 | 段错误 | 0 / 4 |
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ds;
vector<vector<pair<int,int>>> path; // to & dist
int main(){
cin>>n>>m>>k>>ds;
path.resize(n+m+1);
while(k--){
string p1,p2;
int dist,end1,end2;
cin>>p1>>p2>>dist;
if(p1.length()>1){
p1=p1.substr(1,p1.length());
end1=stoi(p1)+n;
}else{
end1=stoi(p1);
}
if(p2.length()>1){
p2=p2.substr(1,p2.length());
end2=stoi(p2)+n;
}else{
end2=stoi(p2);
}
path[end1].push_back(make_pair(end2,dist));
path[end2].push_back(make_pair(end1,dist));
}
int final_dist=0,final_sum,final_bin=0;
for(int i=n+1;i<=n+m;i++){
vector<int> dist(n+m+1,0x3f3f3f3f);
queue<int> q;
bool flag=true;
q.push(i);
dist[i]=0;
while(!q.empty()){
int now=q.front();
q.pop();
for(auto &p:path[now]){
if(dist[now]+p.second<dist[p.first]){
dist[p.first]=dist[now]+p.second;
q.push(p.first);
}
}
}
int mindist=0x3f3f3f3f,sum=0;
for(int i=1;i<=n;i++){
if(dist[i]>ds){
flag=false;
break;
}
mindist=(mindist>dist[i])?dist[i]:mindist;
sum+=dist[i];
}
if(flag){
if(mindist>final_dist || (mindist==final_dist && sum<final_sum)){
final_bin=i-n;
final_dist=mindist;
final_sum=sum;
}
}
}
if(final_dist!=0)
printf("G%d\n%.1lf %.1lf\n",final_bin,final_dist*1.0,final_sum*1.0/n);
else
printf("No Solution\n");
return 0;
}Code2
240207
现在是用BFS做的。问题出在p1[0]=='G'上，之前用了p1.length()>1是错误的。
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 452 | 3 | 答案正确 | 16 / 16 | |
| 1 | 456 | 3 | 答案正确 | 2 / 2 | |
| 2 | 456 | 3 | 答案正确 | 4 / 4 | |
| 3 | 452 | 3 | 答案正确 | 4 / 4 | |
| 4 | 580 | 9 | 答案正确 | 4 / 4 |
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ds;
vector<vector<pair<int,int>>> path; // to & dist
int main(){
cin>>n>>m>>k>>ds;
path.resize(n+m+1);
while(k--){
string p1,p2;
int dist,end1,end2;
cin>>p1>>p2>>dist;
if(p1[0]=='G'){
p1=p1.substr(1,p1.length());
end1=stoi(p1)+n;
}else{
end1=stoi(p1);
}
if(p2[0]=='G'){
p2=p2.substr(1,p2.length());
end2=stoi(p2)+n;
}else{
end2=stoi(p2);
}
path[end1].push_back(make_pair(end2,dist));
path[end2].push_back(make_pair(end1,dist));
}
int final_dist=0,final_sum,final_bin=0;
for(int i=n+1;i<=n+m;i++){
vector<int> dist(n+m+1,0x3f3f3f3f);
queue<int> q;
bool flag=true;
q.push(i);
dist[i]=0;
while(!q.empty()){
int now=q.front();
q.pop();
for(auto &p:path[now]){
if(dist[now]+p.second<dist[p.first]){
dist[p.first]=dist[now]+p.second;
q.push(p.first);
}
}
}
int mindist=0x3f3f3f3f,sum=0;
for(int i=1;i<=n;i++){
if(dist[i]>ds){
flag=false;
break;
}
mindist=(mindist>dist[i])?dist[i]:mindist;
sum+=dist[i];
}
if(flag){
if(mindist>final_dist || (mindist==final_dist && sum<final_sum)){
final_bin=i-n;
final_dist=mindist;
final_sum=sum;
}
}
}
if(final_dist!=0)
printf("G%d\n%.1lf %.1lf\n",final_bin,final_dist*1.0,final_sum*1.0/n);
else
printf("No Solution\n");
return 0;
}Code3
240207
现在使用了Dijkstra算法
| 测试点 | 提示 | 内存(KB) | 用时(ms) | 结果 | 得分 |
|---|---|---|---|---|---|
| 0 | 456 | 3 | 答案正确 | 16 / 16 | |
| 1 | 452 | 3 | 答案正确 | 2 / 2 | |
| 2 | 452 | 3 | 答案正确 | 4 / 4 | |
| 3 | 456 | 3 | 答案正确 | 4 / 4 | |
| 4 | 576 | 22 | 答案正确 | 4 / 4 |
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ds;
vector<vector<pair<int,int>>> path; // to & dist
vector<int> dijkstra(int root){
vector<int> dist(n+m+1,0x3f3f3f3f);
vector<bool> used(n+m+1,false);
dist[root]=0;
for(int i=1;i<=n+m;i++){
int cur=-1;
for(int j=1;j<=n+m;j++)
if(!used[j] && (cur==-1 || dist[j]<dist[cur]))
cur=j;
used[cur]=true;
for(auto &k:path[cur]){
dist[k.first]=min(dist[k.first],dist[cur]+k.second);
}
}
return dist;
}
int main(){
cin>>n>>m>>k>>ds;
path.resize(n+m+1);
while(k--){
string p1,p2;
int dist,end1,end2;
cin>>p1>>p2>>dist;
if(p1[0]=='G'){
p1=p1.substr(1);
end1=stoi(p1)+n;
}else{
end1=stoi(p1);
}
if(p2[0]=='G'){
p2=p2.substr(1);
end2=stoi(p2)+n;
}else{
end2=stoi(p2);
}
path[end1].push_back(make_pair(end2,dist));
path[end2].push_back(make_pair(end1,dist));
}
int final_dist=0,final_sum,final_bin=0;
for(int i=n+1;i<=n+m;i++){
bool flag=true;
vector<int> dist=dijkstra(i);
int mindist=0x3f3f3f3f,sum=0;
for(int j=1;j<=n;j++){
if(dist[j]>ds){
flag=false;
break;
}else{
mindist=min(mindist,dist[j]);
sum+=dist[j];
}
}
if(flag){
if(mindist>final_dist || (mindist==final_dist && sum<final_sum)){
final_bin=i-n;
final_dist=mindist;
final_sum=sum;
}
}
}
if(final_dist!=0)
printf("G%d\n%.1lf %.1lf\n",final_bin,final_dist*1.0,final_sum*1.0/n);
else
printf("No Solution\n");
return 0;
}