第五次双周赛
目录L 1-3 帅到没朋友
- 看题不仔细！！
- 坑1: 00000到99999，都是五位数，不足需要补0
- 坑2: 用sum记输出数量来决定是否输出空格，不能用m!=1记，因为最后一个被判断的数不一定是需要输出的最后一个数！
#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,int>mp;
int main()
{
cin>>n;
while(n--)
{
int k,x;
cin>>k;
if(k==1)
{
cin>>x;
continue;
}
while(k--)
{
cin>>x;
mp[x]=1;
}
}
cin>>m;
int sum=0;
while(m--)
{
int x;
cin>>x;
if(!mp[x])
{
if(sum!=0) cout<<" ";
mp[x]=1;
printf("%05d",x);
// if(m!=1)
// cout<<" ";
}
}
if(sum==0)
cout<<"No one is handsome";
return 0;
}
L 1-7 连续因子
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int N, i, j, num, count, start = 0, max = 0;
scanf("%lld", &N);
for (i = 2; i < sqrt(N); i++)
{
num = 1;
count = 0;
for (j = i; N % (num * j) == 0; j++)
{
count++;
num *= j;
}
if (count > max)
{
start = i;
max = count;
}
}
if (max == 0)
{
printf("1\n");
printf("%lld\n", N);
}
else
{
printf("%lld\n", max);
for (i = start; i < start + max - 1; i++)
{
printf("%lld*", i);
}
printf("%lld\n", i);
}
return 0;
}
L 2-1 红色警报（并查集）
-
思路：输入时用并查集合并，并统计现在有多少块。
每删一个城市都要重新合并一次，再统计当前块数。
-
注意:不需要查找时尽量用unordered_map，不然可能会运行超时
#include<bits/stdc++.h> using namespace std; unordered_map<int,int>de; unordered_map<int,int>father; struct Node{ int x,y; }node[5010]; int findroot(int x) { // if(x!=father[x]) // father[x]=findroot(father[x]); // return father[x]; while(father[x]!=x) { x=father[x]; } return x; } void unionroot(int a,int b) { int x,y; x=findroot(a); y=findroot(b); if(x==y) return; if(x>y) swap(x,y);//大的为根 father[x]=y; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m,n,k,num1=0; cin>>n>>m; for(int i=0;i<n;i++) father[i]=i; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; node[i].x =a; node[i].y =b; unionroot(a,b); } //统计块的个数 for(int i=0;i<n;i++) { if(father[i]==i) num1++; } cin>>k; for(int i=0;i<k;i++) { int x,num2=0; cin>>x; de[x]=1; for(int i=0;i<n;i++) father[i]=i; for(int i=0;i<m;i++) { if(de[node[i].x]==1||de[node[i].y] ==1) continue; unionroot(node[i].x ,node[i].y ); } for(int i=0;i<n;i++) { if(father[i]==i) num2++; } if(num2==num1+1||num2==num1) cout<<"City "<<x<<" is lost.\n"; else cout<<"Red Alert: City "<<x<<" is lost!\n"; num1=num2;//更新当前块的个数 } if(k>=n) cout<<"Game Over."; return 0; }
L 2-2 秀恩爱分得快
-
stoi()函数：把string转为int型
stol()：string转为long int
stoll()：string转为long long
-
性别区分：0 和-0是不一样的，要用string接收不能用int
-
时间复杂度：应该先存照片信息，如果照片中有a或b，再遍历照片。如果输入时就全部存进去后面会超时。
#include<bits/stdc++.h> using namespace std; const int maxn = 1001; int sex[maxn] = {0}; double relateA[maxn] = {0}; double relateB[maxn] = {0}; vector<int> v[maxn]; int A,B; void print(int a, int b){ if(sex[a]) cout << "-"; cout << a << " "; if(sex[b]) cout << "-"; cout << b << endl; } int main() { int n, m, k; cin >> n >> m; char s[10]; for(int i=0;i<m;i++){ cin >> k; for(int j=0;j<k;j++){ cin >> s; int t = abs(atoi(s)); if(s[0] == '-') sex[t] = 1; v[i].push_back(t); } } cin >> s; A = abs(atoi(s)); if(s[0] == '-') sex[A] = 1; cin >> s; B = abs(atoi(s)); if(s[0] == '-') sex[B] = 1; double maxA = 0,maxB = 0; for(int i=0;i<m;i++){ bool founda = find(v[i].begin(),v[i].end(),A) != v[i].end(); bool foundb = find(v[i].begin(),v[i].end(),B) != v[i].end(); if(founda || foundb){ for(int j = 0; j < v[i].size(); j++){ int c = v[i][j]; if(founda && sex[A] != sex[c]){ relateA[c] += (double)1 / v[i].size(); maxA = max(maxA,relateA[c]); } if(foundb && sex[B] != sex[c]){ relateB[c] += (double)1 / v[i].size(); maxB = max(maxB,relateB[c]); } } } } if(relateA[B] == maxA &&relateB[A] == maxB) { print(A,B); }else{ for(int i=0; i<n; i++){ if(maxA == relateA[i]) print(A,i); } for(int i=0; i<n; i++){ if(maxB == relateB[i]) print(B,i); } } return 0; }
L 2-3 插松枝
- 题目好长...
- 三个输出条件：1.盒子中的不满足，推送器没有松针片；2.小盒子满了；3.干上插满了
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int Max=1e6+5;
const ll INF=1e10;
stack<int>s;//盒子
queue<int>q;//推子
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<n;i++){
int t;cin>>t;
q.push(t);
}
while(1){
vector<int>v;
while(!s.empty()){
int num=s.top();
if(v.size()==0) v.pb(num),s.pop();
else{
if(num<=v[v.size()-1]&&v.size()<k){
v.pb(num),s.pop();
}else break;
}
}//先送盒子里面取松针
if(v.size()==k){
for(int i=0;i<k;i++){
if(i==0) cout<<v[i];
else cout<<" "<<v[i];
}
cout<<endl;
}//松枝满了直接输出，不满再从推子里面取
else{
while(!q.empty()){
int num=q.front();
if(v.size()==0) v.pb(num),q.pop();
else{
if(v.size()==k) break;
if(num<=v[v.size()-1]){
v.pb(num),q.pop();
}else{
if(s.size()<m){
s.push(num);q.pop();
}else break;
}
}
}
if(v.size()==0) break;
for(int i=0;i<v.size();i++){
if(i==0) cout<<v[i];
else cout<<" "<<v[i];
}
cout<<endl;
}
}
}
L 2-4 哲哲打游戏
- 纯纯模拟、、遇到存档就直接输出
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[110];//表示档位i存的剧情点
int main()
{
cin>>n>>m;
vector<vector<int>> jq;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
vector<int>x;
while(k--)
{
int y;
cin>>y;
x.push_back(y);
}
jq.push_back(x);
}
int now=1;
while(m--)
{
int x,y;
cin>>x>>y;
if(x==0)
{
now=jq[now-1][y-1];
}
if(x==1)
{
a[y]=now;
cout<<now<<endl;
}
if(x==2)
{
now=a[y];
}
}
cout<<now<<endl;
return 0;
}