C/C++编程八级 题库
生理周期(2022.12)
人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度集中。因为三个周期的周长不同,所以通常三个周期的高峰不会落在同一天。对于每个人,我们想知道何时三个高峰落在同一天。对于每个周期,我们会给出从当前年份的第一天开始,到出现高峰的天数(不一定是第一次高峰出现的时间)。你的任务是给定一个从当年第一天开始数的天数,输出从给定时间开始(不包括给定时间)下一次三个高峰落在同一天的时间(距给定时间的天数)。例如:给定时间为10,下次出现三个高峰同天的时间是12,则输出2(注意这里不是3)。
时间限制:1000
内存限制:65536
输入
一行,包含四个整数:p, e, i和d,相邻两个整数之间用单个空格隔开。 p, e, i分别表示体力、情感和智力高峰出现的时间(时间从当年的第一天开始计算)。d 是给定的时间,可能小于p, e, 或 i。 所有给定时间是非负的并且小于等于365, 所求的时间小于等于21252。
输出
一个整数,即从给定时间起,下一次三个高峰同天的时间(距离给定时间的天数)。
样例输入
4 5 6 7
样例输出
16994
#include <iostream>
using namespace std;
int main() {
int p, e, i, d;
cin >> p >> e >> i >> d;
int k = d + 1;
for (; k <= 21252; k++)
if ((k - p) % 23 == 0 && (k - e) % 28 == 0 && (k - i) % 33 == 0)
break;
cout << k - d << endl;
return 0;
}开关问题
有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)
时间限制:1000
内存限制:65536
输入
输入第一行有一个数K,表示以下有K组测试数据。 每组测试数据的格式如下: 第一行 一个数N(0 < N < 29) 第二行 N个0或者1的数,表示开始时N个开关状态。 第三行 N个0或者1的数,表示操作结束后N个开关的状态。 接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。
输出
如果有可行方法,输出总数,否则输出“Oh,it's impossible~!!” 不包括引号
样例输入
2 3 0 0 0 1 1 1 1 2 1 3 2 1 2 3 3 1 3 2 0 0 3 0 0 0 1 0 1 1 2 2 1 0 0
样例输出
4 Oh,it's impossible~!!
提示
第一组数据的说明:一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3 (不记顺序)
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 35;
bool a[MAXN][MAXN];
inline int read() {
int x;
scanf("%d", &x);
return x;
}
int gauss(int n) {
int rank = 0;
for (int d = 0; d < n; ++d) { /* d for diagonal */
int i;
/* try to find first line whose d'th element = 1 */
for (i = d; i < n; ++i)
if (a[i][d] == 1)
break;
/* not found */
if (i == n)
continue;
/* found */
/* Step 1: make the d'th element of rank'th line to be 1, by swapping i'th
* line and rank'th line, including the rightmost column */
for (int j = 0; j <= n; ++j)
swap(a[rank][j], a[i][j]);
/* Step 2: eliminating the following line if the d'th element = 1, including
* the rightmost column */
for (i = rank + 1; i < n; ++i)
if (a[i][d])
for (int j = 0; j <= n; ++j)
a[i][j] ^= a[rank][j];
++rank;
}
/* up to now, the rank+'th line should be all 0 */
/* if the rightmost column is 1, bad equation, return -1 */
for (int i = rank; i < n; ++i)
if (a[i][n])
return -1;
/* otherwise, return the rank */
return rank;
}
int main() {
int K = read();
for (int k = 0; k < K; ++k) {
memset(a, 0, sizeof(a));
int N = read();
for (int i = 0; i < N; ++i)
a[i][N] ^= read();
for (int i = 0; i < N; ++i)
a[i][N] ^= read();
for (int x = 0; x < N; ++x)
a[x][x] = 1;
for (;;) {
int x = read() - 1, y = read() - 1;
if (x == -1)
break;
a[y][x] = 1;
}
int rank = gauss(N);
if (rank == -1)
printf("Oh,it's impossible~!!\n");
else
printf("%d\n", 1 << (N - rank));
}
system("pause");
return 0;
}冰阔落I
老王喜欢喝冰阔落。
初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。
有m 次操作,每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。
最后,老王想知道哪些杯子有冰阔落。
时间限制:10000
内存限制:65536
输入
有多组测试数据,少于5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。
输出
每组测试数据,前m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。
样例输入
3 2
1 2
2 1
4 2
1 2
4 3
样例输出
No
Yes
2
1 3
No
No
2
1 4
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000 + 5], cnt;
int root(int x) {
if (a[x] == x)
return x;
return root(a[x]);
}
void find(int l, int r) {
int ll = root(l), rr = root(r);
if (ll == rr) {
printf("Yes\n");
// cout<<"Yes"<<endl;
} else {
a[rr] = ll;
cnt--;
// cout<<"No"<<endl;
printf("No\n");
}
}
int main() {
int m, n, l, r;
while (scanf("%d %d", &n, &m) != EOF) {
cnt = n;
for (int i = 1; i <= n; i++) {
a[i] = i;
}
for (int i = 1; i <= m; i++) {
scanf("%d %d", &l, &r);
// cin>>l>>r;
find(l, r);
}
printf("%d\n", cnt);
// cout<<cnt<<endl;
for (int i = 1; i <= n; i++)
if (a[i] == i)
printf("%d ", i); // cout<<i<<" ";
// cout<<endl;
printf("\n");
}
return 0;
}最短路
给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.
时间限制:2000
内存限制:65536
输入
第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.
输出
对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.
样例输入
4
5 7 1
1 2 3
2 3 4
3 4 8
1 3 9
4 5 1
1 4 5
1 5 10
4 4 1
1 2 -4
2 3 8
1 3 5
3 4 0
3 3 2
1 2 -3
2 3 -4
3 1 6
4 2 1
1 2 1
3 4 2
样例输出
0 3 7 5 6
0 -4 4 4
Error
0 1 null null
//C语言参考答案
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define MAXN 10001
#define MAXM 20001
typedef struct {
int u, v, w;
} Edge;
int dist[MAXN];
Edge edges[MAXM];
void BellmanFord(int n, int m, int s) {
int i, j;
// 初始化距离数组
for (i = 1; i <= n; i++) {
dist[i] = INT_MAX;
}
dist[s] = 0;
// 进行n-1轮松弛操作
for (i = 1; i <= n - 1; i++) {
for (j = 0; j < m; j++) {
int u = edges[j].u;
int v = edges[j].v;
int w = edges[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// 检查是否存在负圈
bool hasNegativeCycle = false;
for (j = 0; j < m; j++) {
int u = edges[j].u;
int v = edges[j].v;
int w = edges[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
hasNegativeCycle = true;
break;
}
}
// 输出结果
if (hasNegativeCycle) {
printf("Error\n");
} else {
for (i = 1; i <= n; i++) {
if (dist[i] != INT_MAX) {
printf("%d ", dist[i]);
} else {
printf("null ");
}
}
printf("\n");
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m, s;
scanf("%d %d %d", &n, &m, &s);
int i;
for (i = 0; i < m; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
}
BellmanFord(n, m, s);
}
return 0;
}道路
N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)
Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。
时间限制:1000
内存限制:65536
输入
第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。
输出
输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。
样例输入
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
样例输出
11
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{
int d,L,t;
};
int N,K,R;
vector < vector <Road> > G(110);//用二维数组表示临界表,G[s]表示和s邻接的路
int minLen;//全局变量,记录最短的路径长度
int totalCost;//当前状态的花费
int totalLen;//当前状态的长度
int visited[110];
int minL[110][10010];//minL[i][j]的意义是当到达i点是花费为j时的最短路径
void Dfs(int s)
{
if(s==N)
{
minLen=min(minLen,totalLen);
return ;
}
int len=G[s].size();
for(int i=0;i<len;i++)//枚举和s相邻接额情况
{
Road r=G[s][i];
if(!visited[r.d])//如果没有被走过
{
/*下面三个if语句是三条剪枝条件*/
if(totalCost+r.t>K)//如果当前花销大于K了
continue;
if(totalLen+r.L>=minLen)//如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了
continue;
//如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue
if(totalLen+r.L>minL[r.d][totalCost+r.t])
continue;
minL[r.d][totalCost+r.t]=totalLen+r.L;
visited[r.d]=1;
totalCost+=r.t;
totalLen+=r.L;
Dfs(r.d);
visited[r.d]=0;//因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态
totalCost-=r.t;
totalLen-=r.L;
}
}
}
int main()
{
cin>>K>>N>>R;
for(int i=0;i<R;i++)
{
int s;
Road r;
cin>>s;
cin>>r.d>>r.L>>r.t;
G[s].push_back(r);
}
totalCost=0;
totalLen=0;
minLen=1<<30;//无穷大
memset(visited,0,sizeof(visited));
for(int i=1;i<=N;i++)
for(int j=0;j<10010;j++)
minL[i][j]=1<<30;
visited[1]=1;
Dfs(1);
if(minLen<(1<<30))
cout<<minLen<<endl;
else
cout<<-1<<endl;
return 0;
}Rainbow的商店
Rainbow开了一家商店,在一次进货中获得了N个商品。
已知每个商品的利润和过期时间。
Rainbow每天只能卖一个商品,并且过期商品不能再卖。
Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。
由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rainbow最终可以获得的最大收益。
时间限制:1000
内存限制:262144
输入
第一行两个整数N。 接下来N行每行两个整数,分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。
输出
输出一个整数,表示Rainbow最终可以获得的最大收益。
样例输入
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
样例输出
185
提示
第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50(实际上只要在第10天卖就可以) 第5天卖出5(实际上只要在第20天前卖就可以) 总计185 其它2件商品由于过期、每天只能卖一个的限制,在最优策略下应该不出售。
#include<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{
int w;
int d;
friend bool operator <(const Goods a, const Goods b)
{
if (a.w != b.w)
{
return a.w < b.w;//大的天数小的在前
}
else
{
return a.d > b.d;
}
}
}good[10005];
bool vis[10005] = {};
int main()
{
cin >> N;
priority_queue<Goods>que;
int maxval=0;
for (int i = 1; i <= N; i++)
{
scanf("%d %d", &good[i].w, &good[i].d);
que.push(good[i]);
}
while (!que.empty())
{
Goods now = que.top();
que.pop();
for (int i = now.d; i >= 1; i--)
{
if (!vis[i])
{
vis[i] = 1;
maxval += now.w;
break;
}
}
}
printf("%d\n", maxval);
return 0;
}冰阔落 I
老王喜欢喝冰阔落。
初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。
有m 次操作,每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。
最后,老王想知道哪些杯子有冰阔落。
时间限制:10000
内存限制:65536
输入
有多组测试数据,少于 5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。
输出
每组测试数据,前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。
样例输入
3 2 1 2 2 1 4 2 1 2 4 3
样例输出
No Yes 2 1 3 No No 2 1 4
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{
if(a[x]==x) return x;
return root(a[x]);
}
void find(int l,int r)
{
int ll=root(l),rr=root(r);
if(ll==rr)
{
printf("Yes\n");
//cout<<"Yes"<<endl;
}
else
{
a[rr] =ll;
cnt--;
//cout<<"No"<<endl;
printf("No\n");
}
}
int main()
{
int m,n,l,r;
while(scanf("%d %d",&n,&m)!=EOF)
{
cnt=n;
for(int i=1;i<=n;i++)
{
a[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d %d",&l,&r);
//cin>>l>>r;
find(l,r);
}
printf("%d\n",cnt);
//cout<<cnt<<endl;
for(int i=1;i<=n;i++)
if(a[i]==i) printf("%d ",i);//cout<<i<<" ";
//cout<<endl;
printf("\n");
}
return 0;
}青蛙的约会(2023年5月8级)
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
时间限制:1000
内存限制:65536
输入
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
样例输入
1 2 3 4 5
样例输出
4
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return gcd;
}
ll inv(ll a, ll b, ll c) {
ll x, y;
ll gcd = exgcd(a, b, x, y);
if(c % gcd != 0) return -1;
x *= c / gcd; //得到当前情况下的一个x
b /= gcd; //根据通解x = x0 + (b * t) / gcd 所以b = b / gcd
b = abs(b); //为了得到正数解,所以要abs,而且要在上一步/gcd之后,因为gcd可能是负的
ll ans = x % b;
if(ans < 0) ans += b;
return ans;
}
int main() {
ll x, y, n, m, L;
cin >> x >> y >> m >> n >> L;
ll res = inv(m - n, L, y - x);
if(res == -1)
cout << "Impossible";
else
cout << res;
return 0;
}最短路径问题
平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
时间限制:1000
内存限制:131072
输入
共n+m+3行,其中: 第一行为整数n。 第2行到第n+1行(共n行) ,每行两个整数x和y,描述了一个点的坐标。 第n+2行为一个整数m,表示图中连线的个数。 此后的m 行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。 最后一行:两个整数s和t,分别表示源点和目标点。
输出
仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。
样例输入
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
样例输出
3.41
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, ex, x, y;
double range[101][101], dot[101][3];
double findrange(int sx, int ex) {
int a = (dot[ex][1] - dot[sx][1]);
int b = (dot[ex][2] - dot[sx][2]);
return sqrt(a * a + b * b);
}
int main() {
memset(range, 127, sizeof(range));
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 2; j++) {
cin >> dot[i][j];
}
range[i][i] = 0;
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> sx >> ex;
range[sx][ex] = range[ex][sx] = findrange(sx, ex); // 无向图
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (k != i && k != j && i != j) {
range[i][j] = min(range[i][j], range[i][k] + range[k][j]);
}
}
}
} // 弗洛伊德算法核心:三重循环遍历;外层循环是k可以理解为,中间点是k是遍历所有i和j
cin >> x >> y;
printf("%.2lf", range[x][y]);
return 0;
}//参考答案2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;
int x[N],y[N];
double g[N][N];
double calculate(int x1,int y1,int x2,int y2)
{
return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
int main()
{
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
cin>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
g[i][j]=INF;
g[j][i]=INF;
}
g[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
double temp=calculate(x[u],y[u],x[v],y[v]);
g[u][v]=temp;
g[v][u]=temp;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
int u,v;
cin>>u>>v;
printf("%.2lf",g[u][v]);
return 0;
}Freda的越野跑(2023.3)
Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。
假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?
时间限制:1000
内存限制:262144
输入
第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。
输出
一个整数,表示有多少对参赛者之间发生赶超事件。
样例输入
5 1 3 10 8 5
样例输出
7
提示
我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。
#include <iostream>
#define N 100002
int a[N] = {0}, t[N] = {0};
long long c = 0;
void merge(int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r)
if (a[i] > a[j])
t[k++] = a[i++];
else {
t[k++] = a[j++];
c += 1 + m - i;
}
while (i <= m)
t[k++] = a[i++];
while (j <= r)
t[k++] = a[j++];
for (i = l; i <= r; ++i)
a[i] = t[i];
}
void divide(int l, int r) {
int m;
if (r > l) {
m = (r + l) / 2;
divide(l, m);
divide(m + 1, r);
merge(l, m, r);
}
}
int main() {
int n, i = 0;
std::cin >> n;
while (i < n)
std::cin >> a[i++];
divide(0, n - 1);
std::cout << c;
}社交网络
随着社交平台的兴起,人们之间的沟通变得越来越密切。通过Facebook的分享功能,只要你是对方的好友,你就可以转发对方的状态,并且你的名字将出现在“转发链”上。经过若干次转发以后,很可能A分享了一条好友C的状态,而C的这条状态实际上是分享B的,但A与B可能并不是好友,即A通过C间接分享了B的状态。
给定你N个人之间的好友关系,好友关系一定是双向的。只要两个人是好友,他们就可以互相转发对方的状态,无论这条状态是他自己的,还是他转发了其他人的。现在请你统计,对于每两个人,他们是否有可能间接转发对方的状态。
时间限制:1000
内存限制:262144
输入
第一行1个整数N(1<=N<=300)。 接下来N行每行N个整数,表示一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人是好友,0则表示不是好友。 保证矩阵的主对角线上都是1,并且矩阵关于主对角线对称。
输出
一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人可能间接转发对方的状态,0则表示不可能。
样例输入
5 11000 11100 01100 00011 00011
样例输出
11100 11100 11100 00011 00011
提示
在输入数据中,1与2是好友,2与3是好友,4与5是好友。 因此1、2、3有可能互相转发状态;4、5有可能互相转发状态。这两组人之间则不可能。
#include <bits/stdc++.h>
using namespace std;
int n, fa[310];
char a[310][310];
int find(int x) {
if (x == fa[x]) {
return x;
}
return find(fa[x]);
}
void merge(int x, int y) {
if (find(x) == find(y)) {
return;
}
fa[find(x)] = find(y);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == 49 && i != j) {
merge(i, j);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (find(i) == find(j)) {
cout << 1;
} else {
cout << 0;
}
}
cout << '\n';
}
}旅行
转眼毕业了,曾经朝夕相处的同学们不得不都各奔东西,大家都去了不同的城市开始新的生活。在各自城市居住了一段时间后,他们都感到了一些厌倦,想去看看其他人的生活究竟如何,于是他们都选择到另一个同学所在城市去旅游,并且希望旅游的城市各不相同,他们想知道有多少种不同的方案,可是数量实在太多了,他们无法计算出来,你能帮助他们吗。
时间限制:10000
内存限制:131072
输入
一个正整数n(n<200),表示人数。
输出
一个数,表示有多少不同的方案。
样例输入
3
样例输出
2
提示
有如下两种方案: 同学1去同学2的城市,同学2去同学3的城市,同学3去同学1的城市; 同学1去同学3的城市,同学3去同学2的城市,同学2去同学1的城市。
#include <iostream>
using namespace std;
unsigned long long a[22];
long long ans(int x) {
if (a[x])
return a[x];
else if (x == 1)
return a[x] = 0;
else if (x == 2)
return a[x] = 1;
else if (x == 3)
return a[x] = 2;
else
return a[x] = ans(x - 1) * (x - 1) + ans(x - 2) * (x - 1);
}
int main() {
int n;
cin >> n;
ans(20);
cout << ans(n);
// printf("%llu",ans(n));
return 0;
}最短路径问题
平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
时间限制:1000
内存限制:131072
输入
共n+m+3行,其中: 第一行为整数n。 第2行到第n+1行(共n行) ,每行两个整数x和y,描述了一个点的坐标。 第n+2行为一个整数m,表示图中连线的个数。 此后的m 行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。 最后一行:两个整数s和t,分别表示源点和目标点。
输出
仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。
样例输入
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5
样例输出
3.41
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, ex, x, y;
double range[101][101], dot[101][3];
double findrange(int sx, int ex) {
int a = (dot[ex][1] - dot[sx][1]);
int b = (dot[ex][2] - dot[sx][2]);
return sqrt(a * a + b * b);
}
int main() {
memset(range, 127, sizeof(range));
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 2; j++) {
cin >> dot[i][j];
}
range[i][i] = 0;
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> sx >> ex;
range[sx][ex] = range[ex][sx] = findrange(sx, ex); // 无向图
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (k != i && k != j && i != j) {
range[i][j] = min(range[i][j], range[i][k] + range[k][j]);
}
}
}
} // 弗洛伊德算法核心:三重循环遍历;外层循环是k可以理解为,中间点是k是遍历所有i和j
cin >> x >> y;
printf("%.2lf", range[x][y]);
return 0;
}//参考答案2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;
int x[N],y[N];
double g[N][N];
double calculate(int x1,int y1,int x2,int y2)
{
return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
int main()
{
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
cin>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
g[i][j]=INF;
g[j][i]=INF;
}
g[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
double temp=calculate(x[u],y[u],x[v],y[v]);
g[u][v]=temp;
g[v][u]=temp;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
int u,v;
cin>>u>>v;
printf("%.2lf",g[u][v]);
return 0;
}控制公司
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下条件之一,公司A就可以控制公司B了:
l 公司A = 公司B。
l 公司A拥有大于50%的公司B的股票。
l 公司A控制K(K >= 1)个公司,记为C1, ..., CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ .... + xK > 50%。(ps:A可以控制自己,即Ci可以为A)
你将被给予一系列的三对数(i,j,p),表明公司i拥有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。
写一个程序读入三对数(i,j,p),并且找出所有的数对(h,s),使得公司h控制公司s。
时间限制:1000
内存限制:65536
输入
第一行: N,表明接下来三对数的数量。 第二行到第N+1行:每行三个整数作为一个三对数(i,j,p),如上文所述。 I,J≤100,N,P≤100
输出
输出零个或更多个的控制其他公司的公司。每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司。将输出的每行以第一个数字升序排列(并且第二个数字也升序排列来避免并列)。请不要输出控制自己的公司。
样例输入
3 1 2 80 2 3 80 3 1 20
样例输出
1 2 1 3 2 3
#include<bits/stdc++.h>
using namespace std;
unsigned long long int n,gf[1000][1000],mp[1000][1000];
void jf(int x,int y)//x公司加上i公司股票
{
for(int i=1;i<=100;i++)
{
if(gf[x][i]+gf[y][i]>100) gf[x][i]=100;//判断
else gf[x][i]+=gf[y][i];
}
return ;
}
void find(int x)//递归
{
for(int i=1;i<=100;i++)
{
if(gf[x][i]>=50&&mp[x][i]==0&&x!=i)
{
mp[x][i]=1;//标记 x公司可以控制i公司
jf(x,i);
find(x);//加上以后再找一遍
return ;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
gf[a][b]=c;
}
int t=1;
while(t<=100)//枚举每一个公司
{
find(t);
t++;
}
for(int i=1;i<=100;i++)
{
for(int j=1;j<=100;j++)
{
if(mp[i][j]==1) cout<<i<<" "<<j<<endl;
}
}
}发现它,抓住它
一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:
1. D [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为
2. A [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为
注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。
时间限制:1000
内存限制:65536
输入
第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。
输出
对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.",如果不是,回答"In different gangs.",如果不确定,回答”Not sure yet."。
样例输入
1 5 5 A 1 2 D 1 2 A 1 2 D 2 4 A 1 4
样例输出
Not sure yet. In different gangs. In the same gang.
#include<bits/stdc++.h>
using namespace std;
template<class T>
struct DisjointSet{
int *parent;
T *data;
map<T,int> m;
int capacity;
int size;
DisjointSet(int max=1000){
capacity=max;
size=0;
parent=new int[max+1];
data=new T[max+1];
}
~DisjointSet(){
delete [] parent;
delete [] data;
}
bool insert(T x){
if(size==capacity) return false;
size++;
data[size]=x;
parent[size]=-1;
m[x]=size;
return true;
}
int getIndex(T x){
for(int i=1;i<=size;i++)
if(data[i]==x)
return i;
return -1;
}
int find(T x){
typename map<T,int>::iterator it;
it=m.find(x);
if(it==m.end()) return -1;
int i,rt;
i=rt=it->second;
while(parent[rt]>0)
rt=parent[rt];
return rt;
}
void unionSet(T x,T y){
int rx,ry;
rx=find(x);
ry=find(y);
if(rx==-1||ry==-1) return ;
if(rx==ry) return ;
if(parent[rx]<parent[ry]){
parent[rx]+=parent[ry];
parent[ry]=rx;
}
else{
parent[ry]+=parent[rx];
parent[rx]=ry;
}
find(x);
find(y);
}
};
int main(){
int t;
cin>>t;
while(t--){
DisjointSet<int> s;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) s.insert(i);
for(int i=1;i<=m;i++){
int a,b;
char c;
cin>>c>>a>>b;
if(c=='D')
s.unionSet(a,b);
else{
if(s.find(a)!=s.find(b)) cout<<"Not sure yet.";
else if(s.parent[a]==s.parent[b]) cout<<"In the same gang.";
else cout<<"In different gangs.";
cout<<endl;
}
}
}
return 0;
}最短路
给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.
时间限制:2000
内存限制:65536
输入
第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.
输出
对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.
样例输入
4 5 7 1 1 2 3 2 3 4 3 4 8 1 3 9 4 5 1 1 4 5 1 5 10 4 4 1 1 2 -4 2 3 8 1 3 5 3 4 0 3 3 2 1 2 -3 2 3 -4 3 1 6 4 2 1 1 2 1 3 4 2
样例输出
0 3 7 5 6 0 -4 4 4 Error 0 1 null null
整理中……
道路(2024.3八级)
N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)
Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。
时间限制:1000
内存限制:65536
输入
第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。
输出
输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。
样例输入
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
样例输出
11
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{
int d,L,t;
};
int N,K,R;
vector < vector <Road> > G(110);//用二维数组表示临界表,G[s]表示和s邻接的路
int minLen;//全局变量,记录最短的路径长度
int totalCost;//当前状态的花费
int totalLen;//当前状态的长度
int visited[110];
int minL[110][10010];//minL[i][j]的意义是当到达i点是花费为j时的最短路径
void Dfs(int s)
{
if(s==N)
{
minLen=min(minLen,totalLen);
return ;
}
int len=G[s].size();
for(int i=0;i<len;i++)//枚举和s相邻接额情况
{
Road r=G[s][i];
if(!visited[r.d])//如果没有被走过
{
/*下面三个if语句是三条剪枝条件*/
if(totalCost+r.t>K)//如果当前花销大于K了
continue;
if(totalLen+r.L>=minLen)//如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了
continue;
//如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue
if(totalLen+r.L>minL[r.d][totalCost+r.t])
continue;
minL[r.d][totalCost+r.t]=totalLen+r.L;
visited[r.d]=1;
totalCost+=r.t;
totalLen+=r.L;
Dfs(r.d);
visited[r.d]=0;//因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态
totalCost-=r.t;
totalLen-=r.L;
}
}
}
int main()
{
cin>>K>>N>>R;
for(int i=0;i<R;i++)
{
int s;
Road r;
cin>>s;
cin>>r.d>>r.L>>r.t;
G[s].push_back(r);
}
totalCost=0;
totalLen=0;
minLen=1<<30;//无穷大
memset(visited,0,sizeof(visited));
for(int i=1;i<=N;i++)
for(int j=0;j<10010;j++)
minL[i][j]=1<<30;
visited[1]=1;
Dfs(1);
if(minLen<(1<<30))
cout<<minLen<<endl;
else
cout<<-1<<endl;
return 0;
}Freda的越野跑(2024.3八级)
Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。
假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?
时间限制:1000
内存限制:262144
输入
第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。
输出
一个整数,表示有多少对参赛者之间发生赶超事件。
样例输入
5 1 3 10 8 5
样例输出
7
提示
我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。
#include <iostream>
#define N 100002
int a[N] = {0}, t[N] = {0};
long long c = 0;
void merge(int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r)
if (a[i] > a[j])
t[k++] = a[i++];
else {
t[k++] = a[j++];
c += 1 + m - i;
}
while (i <= m)
t[k++] = a[i++];
while (j <= r)
t[k++] = a[j++];
for (i = l; i <= r; ++i)
a[i] = t[i];
}
void divide(int l, int r) {
int m;
if (r > l) {
m = (r + l) / 2;
divide(l, m);
divide(m + 1, r);
merge(l, m, r);
}
}
int main() {
int n, i = 0;
std::cin >> n;
while (i < n)
std::cin >> a[i++];
divide(0, n - 1);
std::cout << c;
}Rainbow的商店(2024.3八级)
Rainbow开了一家商店,在一次进货中获得了N个商品。
已知每个商品的利润和过期时间。
Rainbow每天只能卖一个商品,并且过期商品不能再卖。
Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。
由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rainbow最终可以获得的最大收益。
时间限制:1000
内存限制:262144
输入
第一行两个整数N。 接下来N行每行两个整数,分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。
输出
输出一个整数,表示Rainbow最终可以获得的最大收益。
样例输入
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
样例输出
185
提示
第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50(实际上只要在第10天卖就可以) 第5天卖出5(实际上只要在第20天前卖就可以) 总计185 其它2件商品由于过期、每天只能卖一个的限制,在最优策略下应该不出售。
#include<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{
int w;
int d;
friend bool operator <(const Goods a, const Goods b)
{
if (a.w != b.w)
{
return a.w < b.w;//大的天数小的在前
}
else
{
return a.d > b.d;
}
}
}good[10005];
bool vis[10005] = {};
int main()
{
cin >> N;
priority_queue<Goods>que;
int maxval=0;
for (int i = 1; i <= N; i++)
{
scanf("%d %d", &good[i].w, &good[i].d);
que.push(good[i]);
}
while (!que.empty())
{
Goods now = que.top();
que.pop();
for (int i = now.d; i >= 1; i--)
{
if (!vis[i])
{
vis[i] = 1;
maxval += now.w;
break;
}
}
}
printf("%d\n", maxval);
return 0;
}冰阔落 I(2024.3八级)
老王喜欢喝冰阔落。
初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。
有m 次操作,每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。
最后,老王想知道哪些杯子有冰阔落。
时间限制:10000
内存限制:65536
输入
有多组测试数据,少于 5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。
输出
每组测试数据,前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。
样例输入
3 2 1 2 2 1 4 2 1 2 4 3
样例输出
No Yes 2 1 3 No No 2 1 4
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{
if(a[x]==x) return x;
return root(a[x]);
}
void find(int l,int r)
{
int ll=root(l),rr=root(r);
if(ll==rr)
{
printf("Yes\n");
//cout<<"Yes"<<endl;
}
else
{
a[rr] =ll;
cnt--;
//cout<<"No"<<endl;
printf("No\n");
}
}
int main()
{
int m,n,l,r;
while(scanf("%d %d",&n,&m)!=EOF)
{
cnt=n;
for(int i=1;i<=n;i++)
{
a[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d %d",&l,&r);
//cin>>l>>r;
find(l,r);
}
printf("%d\n",cnt);
//cout<<cnt<<endl;
for(int i=1;i<=n;i++)
if(a[i]==i) printf("%d ",i);//cout<<i<<" ";
//cout<<endl;
printf("\n");
}
return 0;
}