|
题目： 海港https://ac.nowcoder.com/acm/problem/16439
题意：
第一行输入一个正整数n，表示小K统计了 n艘船的信息。
接下来n行，每行描述一艘船的信息：前两个整数ti和ki分别表示这艘船到达海港的时间和船上的乘客数量，接下来ki个整数x(i,j)表示船上乘客的国籍。
保证输入的ti是递增的，表示从小K第一次上班开始计时，这艘船在第ti秒到达海港。
计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。
知识点：
STL、队列
题解：
用数组模拟队列来解决滑动窗口问题，题目中只需要按人数来储存国际信息。
代码：
#include<iostream>
using namespace std;
int s,i,n,t,k,r,w[100001],x[300002],y[300002];
int main(){
cin>>n;
while(n--){
cin>>t>>k;
while(k--){
y[++r]=t;cin>>x[r];
if(!w[x[r]])s++;
w[x[r]]++;
}
while(t-y[i]>=86400)
if(!--w[x[i++]])s--;
cout<<s<<endl;
}
return 0;
}
题目： https://ac.nowcoder.com/acm/problem/15973
题意：
一张地图上有有N个城市，他们可以通过双向道路互相连接，但是每两座城市只能有一条双向道路互相连接。
现在我们想要满足条件“地图中不能有任意三个城市可以互相直达”，请问满足这个条件的最大道路数是多少？
知识点：
数学，思维
题解：
通过分析可将本题等价转化为求两段点最多可以连接多少条线段。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 998244353;
int main() {
int n;
while (cin >> n)
cout << (n / 2) * (n - n / 2) << endl;
return 0;
}
题目： https://codeforces.com/contest/1608/problem/C
题意：
N个玩家在玩游戏。
游戏中有两张不同的地图。对于每个玩家，我们知道他在每张地图上的力量。当两名玩家在特定地图上战斗时，在该地图上实力较高的玩家总是获胜。在同一张地图上没有两名玩家拥有相同的力量。
你是游戏大师，想组织一场比赛。总共会有n?1场战斗。当比赛中有一个以上的玩家时，你可以选择任意一张地图和任意两个剩余的玩家在上面战斗。输掉比赛的选手将被淘汰出局。
最后，只剩下一名选手，他被宣布为锦标赛的获胜者。每个选手都要决定自己是否能赢得比赛。
知识点：
图论，结构体排序
题解：
让我们以相反的顺序来看看这些打斗。如果参与人x是赢家，那么他在最后一场比赛中战胜了参与人y。在(n?2)第二次战斗中，x或y战胜了某个玩家z，以此类推。
我们总是通过增加一名至少可以输掉一场比赛的玩家来扩展集合，所以如果我们可以从x开始并以所有玩家的集合结束，x就可以赢得比赛。
如果我们构造一个有向图，即当且仅当u在战斗中战胜v时，从参与人u到参与人v添加一条边，那么问题就相当于找到一个节点集，从这个节点集我们可以到达所有其他节点
为了将边的数量减少到2n?2，我们可以按ai和bi降序对玩家进行排序，并按照这些顺序只添加从第i个玩家到(i+1)-th个玩家的边。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 20;
int tt, n;
pair<int, int> a[N], b[N];
int ind[N], pat[N], ind1[N];
int mn[N], mn1[N];
void solve () {
cin >> n;
for (int i = 0; i < n; i++) {
cin>>a[i].first;
a[i].second=i;
}
for (int i = 0; i < n; i++) {
cin>>b[i].first;
b[i].second=i;
}
sort(a,a+n);
sort(b,b+n);
for (int i = 0; i < n; i++)
ind[b[i].second]=i, ind1[a[i].second]=i;
int mx = 0;
for (int i = n - 1; i >= 0; i--) {
mn[i]=ind[a[i].second];
mn1[i]=ind1[b[i].second];
if(i!=n-1) mn[i]=min(mn[i], mn[i+1]), mn1[i]=min(mn1[i], mn1[i+1]);
}
int i1 = n-1, i2=n-1;
while (i1!=mn[i2]||i2!=mn1[i1]) {
i1=mn[i2];
i2=mn1[i1];
}
for (int i = 0; i < n; i++) pat[i]=0;
for (int i = 0; i < n; i++) {
if(i>=i1) pat[b[i].second]=1;
if(i>=i2) pat[a[i].second]=1;
}
for (int i = 0; i < n; i++) cout<<pat[i];
cout<<endl;
}
int main() {
cin >> tt;
while (tt -- ) {
solve ();
}
return 0;
}
|