@[toc]
概要
- L1部分：L1-081~L1-088
- L2部分：L2-041~L2-044
- L3部分：L3-031~L3-033
L1-081 今天我要赢 (5分)
//希望没人不会做……
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"I'm gonna win! Today!\n";
cout<<"2022-04-23";
return 0;
}L1-082 种钻石（5分）
//总量/速度即可，向下取整
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, v; cin>>n>>v;
cout<<n/v<<"\n";
return 0;
}L1-083 谁能进图书馆(10分)
//题面较长，理清思路后ifelse即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int x, y, a, b; cin>>x>>y>>a>>b;
if(a>=x && b>=x){
cout<<a<<"-Y "<<b<<"-Y\n";
cout<<"huan ying ru guan\n";
}else if(a<x && b < x){
cout<<a<<"-N "<<b<<"-N\n";
cout<<"zhang da zai lai ba\n";
}else{
if(a>=x){
if(a>=y){
cout<<a<<"-Y "<<b<<"-Y\n";
cout<<"qing 1 zhao gu hao 2\n";
}else{
cout<<a<<"-Y "<<b<<"-N\n";
cout<<"1: huan ying ru guan\n";
}
}else{
if(b>=y){
cout<<a<<"-Y "<<b<<"-Y\n";
cout<<"qing 2 zhao gu hao 1\n";
}else{
cout<<a<<"-N "<<b<<"-Y\n";
cout<<"2: huan ying ru guan\n";
}
}
}
return 0;
}L1-084 拯救外星人(10分)
//输出a+b的阶乘，直接枚举即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int a, b; cin>>a>>b;
int c = a+b, d = 1;
for(int i = 1; i <= c; i++)d *= i;
cout<<d<<"\n";
return 0;
}L1-085 试试手气（15分）
//每次摇出来不同，所以直接654往下排，所以直接-n+1，如果大于当前就再-1即可
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
for(int i = 1; i <= 6; i++)cin>>a[i];
int n; cin>>n;
for(int i = 1; i <= 6; i++){
if(i!=1)cout<<" ";
if(6-n+1 > a[i])cout<<6-n+1;
else cout<<6-n+1-1;
}
return 0;
}L1-086 斯德哥尔摩火车上的题(15分)
//代码都给了，照抄就行了
#include<bits/stdc++.h>
using namespace std;
int main(){
string a, sa=""; cin>>a;
for(int i = 1; i < a.size(); i++){
if(a[i]%2==a[i-1]%2){
sa += max(a[i], a[i-1]);
}
}
string b, sb=""; cin>>b;
for(int i = 1; i < b.size(); i++){
if(b[i]%2==b[i-1]%2){
sb += max(b[i], b[i-1]);
}
}
if(sa==sb)cout<<sa<<"\n";
else cout<<sa<<"\n"<<sb;
return 0;
}L1-087 机工士姆斯塔迪奥(20分)
//去掉第1行和第x行对答案的影响是一样的（除非x==1），所以每次n--,m--，最后乘起来即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m, q; cin>>n>>m>>q;
set<int>se, se2;
while(q--){
int t, c; cin>>t>>c;
if(t==0 && !se.count(c))n--,se.insert(c);
if(t==1 && !se2.count(c))m--,se2.insert(c);
}
cout<<n*m<<"\n";
return 0;
}L1-088 静静的推荐(20分)
//gplt175+pat(s)从大到小排个序1次直接推走，剩下pat不够的每个分数都再推k个人即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, k, s; cin>>n>>k>>s;
int a[300]={0}, sum = 0;
for(int i = 1; i <= n; i++){
int x, y; cin>>x>>y;
if(x>=175 && y>=s)sum++;
if(x>=175 && y<s)a[x]++;
}
for(int i = 175; i <= 290; i++){
if(a[i]==0)continue;
if(a[i]<=k)sum += a[i];else sum += k;
}
cout<<sum<<"\n";
return 0;
}L2-041 插松枝(25分)
//队列（推送器）以及栈（小盒子）模拟
#include<bits/stdc++.h>
using namespace std;
stack<int>st;
queue<int>q;
vector<int>ans[1010];
int main(){
int n, m, k; cin>>n>>m>>k;
while(n--){ int x; cin>>x; q.push(x); }
int i = 0, lst = 0;
while(q.size() || st.size()){
lst = (ans[i].size()==0 ? 99999 : ans[i].back());
if(st.size() && st.top()<=lst){ //先用小盒子
ans[i].push_back(st.top()); st.pop();
}else if(q.size() && q.front()<=lst){//再用推送器
ans[i].push_back(q.front()); q.pop();
}else if(st.size()<m && q.size()){//推送器放到小盒子里
st.push(q.front()); q.pop();
}else{
i++;//小盒子满了，下一根
}
if(ans[i].size()==k)i++;
}
for(int j = 0; j <= i; j++){
if(ans[j].size()==0)continue;
for(int k = 0; k < ans[j].size(); k++){
if(k)cout<<" ";
cout<<ans[j][k];
}
cout<<"\n";
}
return 0;
}L2-042 老板的作息表(25分)
//直接排序，然后输出两个不相邻区间的尾和头即可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{int h1, m1, s1, h2, m2, s2; }a[maxn];
bool cmp(node x, node y){
if(x.h1 != y.h1)return x.h1<y.h1;
if(x.m1 != y.m1)return x.m1<y.m1;
if(x.s1 != y.s1)return x.s1<y.s1;
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
scanf("%d:%d:%d - %d:%d:%d", &a[i].h1, &a[i].m1, &a[i].s1, &a[i].h2, &a[i].m2, &a[i].s2);
}
a[0].h1 = 0, a[0].m1 = 0, a[0].s1 = 0;
a[0].h2 = 0, a[0].m2 = 0, a[0].s2 = 0;
a[n+1].h1 = 23, a[n+1].m1 = 59, a[n+1].s1 = 59;
sort(a,a+n+2, cmp);
for(int i = 1; i <= n+1; i++){
if(a[i].h1==a[i-1].h2 && a[i].m1==a[i-1].m2 && a[i].s1==a[i-1].s2)continue;
printf("%02d:%02d:%02d - %02d:%02d:%02d\n", a[i-1].h2, a[i-1].m2, a[i-1].s2, a[i].h1, a[i].m1, a[i].s1);
}
return 0;
}L2-043 龙龙送外卖(25分)
//题意：一棵树上不断加点，求每次加点后访问所有点至少一次的最短距离是多少
//思路：可以贪心，外卖员最后的位置应该在距离外卖站最远的送餐地址。所以最短路程 = 需要经过的边数*2 - max(外卖站到送餐地址)
//每次搜索新增送餐点到外卖站未被标记的点（记忆化）可以实现O（n）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int f[maxn], rt, dep[maxn];
int vis[maxn], tmp; //tmp每次累加就行
void dfs(int u ,int dis){//暴力跑一遍路程
if(u==rt || vis[u]){
tmp += dis; return ;
}
vis[u] = 1;
dfs(f[u], dis+2);
}
int calc(int u){//点u到rt的距离
if(u==rt || dep[u])return dep[u];
return dep[u] = calc(f[u])+1;
}
int main(){
int n, m; cin>>n>>m;
for(int i = 1; i <= n; i++){
int x; cin>>x; f[i] = x;
if(f[i]==-1)rt=i;
}
int mx = 0; //维护当前最大距离
while(m--){
int x; cin>>x;
dfs(x, 0); //每次从这个点跑就行, 根直接当做普通点处理
mx = max(mx, calc(x));
cout<<tmp-mx<<"\n";
}
return 0;
}L2-044 大众情人(25分)
//用距离感建有向图，Floyd计算全图最短路即可，不知道哪里错了，重写一遍过了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
const int inf = 1e9+10;
struct node{int to, d;};
int e[510][510];
int sex[510];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
e[i][j] = inf;
//floyed
for(int i = 1; i <= n; i++){
string op; cin>>op;
if(op=="F")sex[i] = 0; else sex[i] = 1;//男1
int k; cin>>k;
for(int j = 1; j <= k; j++){
int to, d; char ch;
cin>>to>>ch>>d;
e[i][to] = d;
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(e[i][j] > e[i][k]+e[k][j]){
e[i][j] = e[i][k]+e[k][j];
}
}
}
}
//solve
vector<int>girl, boy;
map<int,int>p;
for(int i = 1; i <= n; i++){
int d = -1;
for(int j = 1; j <= n; j++){
if(sex[j]!=sex[i]){
d = max(d, e[j][i]);
}
}
if(d != -1){
p[i] = d;
if(sex[i])boy.push_back(i);
else girl.push_back(i);
}
}
sort(girl.begin(), girl.end(), [&p](int x, int y){
return p[x]==p[y]? x<y : p[x]<p[y];
});
sort(boy.begin(), boy.end(), [&p](int x, int y){
return p[x]==p[y]? x<y : p[x]<p[y];
});
for(int i = 0; i < girl.size(); i++){
if(p[girl[i]] == p[girl[0]]){
if(i!=0)cout<<" ";
cout<<girl[i];
}else break;
}
cout<<"\n";
for(int i = 0; i < boy.size(); i++){
if(p[boy[i]] == p[boy[0]]){
if(i!=0)cout<<" ";
cout<<boy[i];
}else break;
}
cout<<"\n";
return 0;
}
