西南民族大学第十届校赛(网络赛)题解

题目比较简单。

A.dreamstart的催促

裸的快速幂。注意long long

题目连接

描述

有一天集训队的学弟们正在计算一堆数,但是dreamstart感觉他们算的太慢了,就让他们坐在一起想出一个快速计算的方法,但是由于他们一时想不出来,想让你帮助他们。他们说现在有一个数列,要算出第 i 个数的 i 次幂并且把每个数计算出来的值加到一起,最后答案模10000019。

聪明的你可以帮助他们吗?

输入

第一行有一个整数n,n <= 1e5

接下来一行有n个数,每个数的大小不超过1e16

输出

输出取模之后的和

样例输入

1
2
4
1 6 9 12

样例输出

1
21502
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
const int Mod=10000019;
typedef long long ll;

ll Qpow(ll x,ll n){
ll ans=1ll;
while(n){
if(n&1) ans=(ans*x)%Mod;
x=(x*x)%Mod;
n>>=1;
}
return ans;
}


int main()
{
ll n,x,ans=0;
scanf("%lld",&n);
rep(i,0,n){
scanf("%lld",&x);
ans=(ans+Qpow(x,i+1))%Mod;
}
printf("%lld\n",ans);
return 0;
}

B.TRDD got lost again

处理一下就是BFS裸题,把门看成一个格子,最后路径长度/2.

题目连接

描述

X城市是一个交通十分不便利的城市,城市可以看成一个n m大小的矩阵, 现在TRDD手里有该城市的地图:一个2n+1行, 2 *m+1列大小的地图。现在TRDD所在的格子用S表示,机场所在的格子用T表示。 其他格子用空格表示,地图上左右相邻的两个格子如果不能通行用”|”表示, 上下相邻的两个点如果不能通行用”-“表示,”+“表示格子的四个角。 题目保证城市X最外圈无法通行(具体请看样例输入)。
为了能尽快赶到机场,TRDD想请你帮忙计算出他到达机场最少需要走过多少个格子(包括起点S和终点T)。
如果无法到达机场T,则输出”TRDD Got lost…TAT”(不包括双引号)。

输入

第一行读入两个数n, m(1 <= n, m <= 3000)表示X城市的大小。

之后有2 n + 1行, 每行有2 m + 1个字符, 用来表示TRDD手里的地图

题目保证S和T都有且仅有一个。

输出

如果TRDD能到达机场, 则输出TRDD最少需要经过几个格子
否则输出”TRDD Got lost…TAT”(不包括双引号)

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4 3
+-+-+-+
|S| | |
+ +-+-+
| | | |
+ +-+-+
| |T |
+ +-+ +
| |
+-+-+-+
3 3
+-+-+-+
|S| |
+ + +-+
| | |T|
+ + +-+
| | |
+-+-+-+

样例输出

1
2
8
TRDD Got lost...TAT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=6e3+5;
char Map[N][N];
int n,m,Sx,Sy,Ex,Ey;char x,y;

int M_x[4]={1,0,-1,0},
M_y[4]={0,1,0,-1};

struct node{int x,y,step;};


void bfs(){
queue<node> Q;
Q.push((node{Sx,Sy,1}));
while(!Q.empty()){
node tem=Q.front();
rep(i,0,4){
int X=tem.x+M_x[i];
int Y=tem.y+M_y[i];

if(Map[X][Y]=='*') continue;

if(Map[X][Y]=='T') {
printf("%d\n",tem.step/2+1);
return;
}

Map[X][Y]='*';
Q.push(node{X,Y,tem.step+1});
}
Q.pop();
}
printf("TRDD Got lost...TAT\n");
return;
}

int main()
{
scanf("%d%d",&n,&m);
getchar();
CRL(Map,'*');
rep(i,0,n*2+1){
rep(j,0,m*2+1){
x=getchar();
if(x==' '||x=='T') Map[i][j]=x;
else if(x=='-'||x=='|') Map[i][j]='*';
else if(x=='S'){
Map[i][j]=' ';
Sx=i;
Sy=j;
}
}
getchar();
}

bfs();
return 0;
}


C.Company

dfs

题目连接

描述

在一个偏僻的大山里, 一共有n个村庄, 编号1~n,每个村庄都有一定数量的村民, 其中只有1号村庄有水井,为了方便村民们日常用水,村民们一共修建了n-1根水管, 保证每一村庄都能有水喝。因为水是从高流向低, 所以我们知道1号村庄海拔最高, 与1号村庄直接相连的村庄高度次之, 以此类推。

对于每一个村庄, 如果这个村庄的村民人数<=k, 我们称之为”劳动力不足的村庄”。
现在我们想知道, 如果水井不修在1号村庄, 而是修在任意一个村庄, 那么有水流过的村庄中有多少个村庄是”劳动力不足的村庄”(包括有水井的村庄本身)。

输入

第一行输入两个数n(1 <= n <= 200000)村庄的数量, 以及劳动力的评估标准k(1 <= k <= 1e9)
第二行有n个数, 表示这n个村庄的村民数(1 <= a <= 1e9)
之后有n-1行, 每行两个数字u, v(1 <= u, v <= n) u, v两个村庄之间有一条水管。

输出

输出n个数, 输出假设水井修在第i(1 <= i <= n)个村庄,那么有水流过的村庄中有多少个村庄是”劳动力不足的村庄”。

两个数之间用空格隔开

样例输入

1
2
3
4
5
6
7
8
9
8 10
12 15 11 4 5 19 14 20
3 7
1 5
2 1
6 5
2 3
6 4
8 3

样例输出

1
2 0 0 1 2 1 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
#include<string.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
#define lowbit(x) (x&(-x))
const int N=1e6+5;

struct edge {int To,next;}Edge[N]; //链式前向星存图
int cnt=-1,Begin[N],a[N]={0};

void add(int a,int b){
Edge[++cnt]=(edge{b,Begin[a]});
Begin[a]=cnt;
}

int dfs(int x,int f){ //求子树和
int tem=a[x];
for(int i=Begin[x];~i;i=Edge[i].next)
if(Edge[i].To!=f)
tem+=dfs(Edge[i].To,x);
return a[x]=tem;
}

int main()
{
int s,e,n,k;
scanf("%d%d",&n,&k);
CRL(Begin,-1);
rep(i,1,n+1){
scanf("%d",&a[i]);
a[i]= a[i]<=k;
}

rep(i,1,n){
scanf("%d%d",&s,&e);
add(s,e);
add(e,s);
}
dfs(1,-1);
rep(i,1,n+1) printf("%d%c",a[i]," \n"[i==n]);
return 0;
}

D.>A->B->C-

对于A,就看A喜欢的喜欢的喜欢的人是不是A。

题目连接

描述

一天小A在金色的银杏树下向他喜欢的小姐姐B表白了,“对不起,我喜欢的是C”,B这样说道,小A尴尬的笑了笑转身离开了。他心里默默说着“对不起,C喜欢我。”(233333333)
Love triangle被定义为:如果A喜欢B,B喜欢C,C喜欢A则称为Love triangle。现在让你寻找有没有Love triangle。

输入

第一行一个正整数N(n<=5000),第二行n个数$X_1,X_2,X_3……X_n$代表i喜欢$X_i$。

输出

如果存在Love triangle则输出YES,没有则输出NO。

样例输入

1
2
5
2 4 5 1 3

样例输出

1
YES
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=5e3+5;
int a[N]={0};

int main()
{
int n,Flag=0;
scanf("%d",&n);
rep(i,1,n+1){
scanf("%d",&a[i]);
if(a[a[a[i]]]==i) Flag=1; // i喜欢的喜欢的喜欢的人是不是i
}

puts(Flag? "YES":"NO");
return 0;
}

E.PPY的字符串

字符串模拟

题目连接

描述

Siry特别喜欢数学, 在他很小的时候他就对数字特别感兴趣, 他喜欢念数字。
具体念法是这样的: 给你一个数字, 依次念出每个数字有几个相邻(Siry会大声说出a个b, c个d…), 组合起来形成一个新的数字。
如:
2331的念法就是1个2,2个3,1个1, 形成的新数字就是122311。 再念一次就是1个1,2个2,1个3, 2个1, 形成的数字是11221321。
现在Siry大声的念出了第一次的数字x, Siry总共想要念n次, 你能快速的知道第n次的数字是多少吗?

输入

每行输入两个数字x,n。
1≤ x≤ 109,1≤ n≤ 30

输出

输出一行,包括第n个数字的位数和这个数字。 位数和数字之间用空格隔开。

样例输入

1
222 2

样例输出

1
2 32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
#define LL long long

void add(int x,string &s){
if(x) add(x/10,s);
else return;
s+=char('0'+x%10);
}

string change(string s){
string s1="";
int num,i=0;char c;
while(i<s.size()){
num=0;c=s[i];
while(i<s.size()&&s[i]==c){
i++;num++;
}

add(num,s1);
s1+=c;
}
return s1;
}

int main() {
string s;int n;
cin>>s>>n;
n--;
while(n--) s=change(s);

cout<<s.size()<<" "<<s<<endl;
return 0;
}


F.集训队脱单大法:这是一道只能由学姐我自己出数据的水题

思维题。
很明显,无论怎么分,整个数列最大值一定是一个对的最大值。
分两种情况讨论:

  • 最大值被分到了前面一个组,那么无论怎么分,后面的那个组的最大值 $x$ 一定 $x<=a[n]$ ,那么很明显当 $x==a[n]$ 时,有最优解,此时只有把a[n]单独分成一组。
  • 最大值被分到了后面一个组一样的,当 $x==a[1]$ 时,有最优解;

然后答案就是

$$ans = Max-min(a[1],a[n])$$

题目连接

描述

总所不周知!ZZZZone有了女朋友却谁也不知道。但是ZZZZone在集训队总是和陈大佬走的很近,每天搂搂抱抱十分不成体统!于是就被ZZZZone的女朋友给知道了,但是呢,ZZZZone的女朋友是一个热爱画画的温柔又可爱的女子,于是她决定把ZZZZone大卸两块,没错是两块!!

ZZZZone呢他的长度为 n,并且每个单位长度都有一个相对应的重量,他的小女朋友希望将ZZZZone切成两部分后,两个部分中的最大重量之差的绝对值最大(显然两个部分均不能为空啊),她呢觉得很惆怅,不知道该怎么切最好,所以想让你们来想想办法。

输入

第一行为一个$n\(2 <= n <= 10^5)$,表示ZZZZone的长度,第二行为n个数,表示ZZZZone每个单位长度的重量($0 <= a[i] <= 10^6$)。

输出

输出切成两部分后,每部分的重量的最大值之差的绝对值最大是多少。

样例输入

1
2
4
3 4 1 6

样例输出

1
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;

int main(){
int Star,n,Max=0,x;
scanf("%d%d",&n,&Star);
Max=Star;

for(int i=1;i<n;i++){
scanf("%d",&x);
Max=max(Max,x);
}

printf("%d\n",Max-min(Star,x));

return 0;
}

G.不想再WA了

把A,C,W看看成0,1,2,这样就是三进制数里面不要31.
很明显的数位DP.

题目连接

描述

欢迎参加西南民族大学 2018 年校赛。
对于你来说,做题 WA 了 是一件很痛苦的事,所以你从现在开始不想再看到有题 WA 了。
那么现在给你 A,C,W 三种字符,问组成一个长度为 n(不含 WA,即 W 后一个字符不能为 A ) 的字符串,总共有多少种方案?( T 组数据)

输入

先输入一个 T,表示有 T 组数据。
然后输入需要组成字符串的长度 $n_i$ $(1 <= i <= T)$
$1 <= T <= 10$
$1 <= n_i <= 10$

输出

对于每个 $n_i$ 输出对应的答案

样例输入

1
2
3
2
1
2

样例输出

1
2
3
8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
const int maxn=100;
typedef long long ll;

int a[20];
int dp[20][5];
ll dfs(int pos,int pre,int sta,bool limit){
if(pos==-1) return 1;
if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
int up=limit ? a[pos] : 2;
ll tmp=0;
for(int i=0;i<=up;i++){
if(pre==2 && i==0)continue;
tmp+=dfs(pos-1,i,i==2,limit && i==a[pos]);
}
if(!limit) dp[pos][sta]=tmp;
return tmp;
}

ll solve(int n){
int pos=0;
rep(i,0,n) a[i]=2;

return dfs(n,-1,0,true);
}

int main()
{
int n,T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(dp,-1,sizeof dp);
printf("%d\n",solve(n));
}
return 0;
}

H.Ricky’s RealDan’s Ricky

博弈题。我们可以发现Ricky不能改变奇偶性而RealDan可以(奇数拿掉奇数变偶数)。所以RealDan可以视情况留下奇数或偶数,所以除了只有一堆偶数的情况,都是RealDan赢。

题目连接

描述

The 2019 is coming!Ricky 和 RealDan为了庆祝2018一年的成果,准备去大吃一顿,然而 Ricky 想吃火锅, RealDan 想吃海鲜。为了解决吃什么的难题, 他们向聪明的神秘人(出题人)寻求帮助,神秘人则给他们出了这样一个问题:
现在有 n 个娃娃机,第i(1 <= i <= n) 个娃娃机中有 a[i] 个娃娃。
规则如下:

  • Ricky 和 RealDan 轮流抓娃娃,
  • Ricky 每轮只能从其中一个娃娃机中抓走偶数个娃娃。
  • RealDan 每轮只能从其中一个娃娃机中抓走奇数个娃娃。
  • 每人每轮至少抓走一个娃娃(他们都超级厉害), Ricky 先开始抓。

他们在神秘人的教导下,都已经变得非常聪明。最后谁抓不了娃娃,谁就被视为 loser,并且还要把自己抓到的娃娃送给对方,loser也必须去Winner喜欢的地方吃饭。

现在他们找到你,想让你看一下他们究竟谁可以赢。
Note: All the best wishes give Ricky and RealDan by their old friend ~

输入

第一行一个t,表示t组数据。
每组数据有两行:
第一行一个n(1 <= n <= 100000)代表n个娃娃机
下一行有n个数字,代表每一个娃娃机中的娃娃数量a[i] (1 <= a[i] <= 1e9)

输出

如果最后Ricky获胜,则输出“Ricky is Winner”(不包括双引号),反之则输出“RealDan is Winner”(不包括双引号)。

样例输入

1
2
3
1
2
1 2

样例输出

1
RealDan is Winner
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
int T,n,x;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(i,0,n) scanf("%d",&x);

if(n==1&&(x%2==0)) puts("Ricky is Winner");
else puts("RealDan is Winner");
}

return 0;
}

I.小A的期末作业

模拟

题目连接

描述

期末了, 老师给小A布置了一道期末作业, 让小A设计一个图案, 追求完美的小A想要用编程来完成这个图案:
小A想要设计一个由符号组成的“大于号”图案, 图案的大小为n, 一共有2n-1行, 每行有n个符号, 每一行前面有一些空格。
第一行没有空格, 第二行有一个空格, 第三行有两个空格。。。。 依次类推
图案是轴对称图形。

输入

读入一个数字n(1 <= n <= 100), 表示图案的大小.

输出

输出小A想要的图形

样例输入

1
4

样例输出

1
2
3
4
5
6
7
****
****
****
****
****
****
****
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
int n;
scanf("%d",&n);
rep(i,0,n){
rep(j,0,i+n) putchar(j<i? ' ':'*');
printf("\n");
}

repd(i,0,n-1){
rep(j,0,i+n) putchar(j<i? ' ':'*');
printf("\n");
}

return 0;
}


J.怪盗基德 & 月之瞳宝石

二分。
对于每一个星体,在能源体中二分找离他最近的。

题目连接

描述

在这片寂静的夜色之下,他就这样静静的降临在我的面前,他的眼神就好像能看透了一切,露出了无所畏惧的笑容。一袭白斗篷和一顶白礼帽,不带一丝多余的动作,他的脸在单眼眼睛跟逆光之下。

to 世纪末的魔术师
By the mysterious man

怪盗基德在上次失败后,对美丽的月之瞳宝石非常觊觎,他想要得到它,以世纪末的魔术师的名义。但是却遇到了重重机关阻拦,眼看到了月之瞳宝石盒之前,怪盗基德却停下了脚步。

“世界上有些谜,还是让它永远成为谜比较好”

话音刚落,只见一片白雾,待雾散开之时,他已经消失在月色之中。

在怪盗基德走后,你潜入进去,却发现,上面篆刻着一段奇怪的话:

在缥缈的宇宙中,有一条穿越时空的隧道,在这条隧道中,有着许多星体和能源体,他们都排列在一条直线上,对于每个星体而言,他们都需要能源体的照耀才能够存活于这条时空隧道当中,当然一个能源体可以同时为多个星体提供能源(对于一个能源体来说,也可能没有星体需要它提供能源)。但是,有所限制的是每个能源体只能为与自身相距x之内的星体提供能源。现在需要你找到最小的x,使得每个星体都能够得到能源(即每个星体必须得到至少一个能源体的照耀)。

现在是你作为怪盗基德的徒弟大展身手的时候了。

输入

输入共三行,第一行有两个数n和m(1 <= n, m <= 1e5),分别代表有n个星体,m个能源体。

第二行有n个数a1, a2, … an,代表n个星体的位置。(-2e9 <= a[i] <= 2e9)

第三行有m个数b1, b2, … bm,代表m个能源体的位置。(-2e9 <= b[j] <= 2e9)

输出

输出最小的x,满足每个星体都有至少一个能源体为其提供能源。

样例输入

1
2
3
3 2
-2 2 4
-3 0

样例输出

1
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define INIT(a,x) memset(a,x,sizeof(a))
#define LL long long
const LL mod=10000019;
LL a[100007]={0},b[100007]={0};
int main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
for(int i=0;i<m;i++)scanf("%lld",&b[i]);
sort(a,a+n);sort(b,b+m);
LL ans=-555555;
for(int i=0;i<n;i++){
LL *q=lower_bound(b,b+m,a[i]);
LL tem;
if(q==b)tem=abs(a[i]-*q);
else if(*q<a[i])tem=abs(a[i]-*(q-1));
else tem=min(abs(a[i]-*q),abs(a[i]-*(q-1)));
ans=max(ans,tem);
}
printf("%lld\n",ans);
return 0;
}

K.正方体

模拟too

题目连接

描述

已知一个正方体,每个面上都有任意一个数(假设每一面的面积足够大来装下当前面上的数字),现被展开成了如下形式:

输入中保证第一行有一个面,第二行有四个面,第三行有一个面。请用代码检查这个正方体对立面上的数是否相同。

输入

输入包含多个测试样例。第一行为一个整数T(1 <= T <= 1e4),接下来每个样例占3行,每行都包括4个数,为0表明当前位置不表示面,每个面上的数值范围不超过int。

Eg:上图的输入为:
0 1 0 0
2 4 2 4
0 0 1 0

输出

对于每个测试样例,如果当前正方体的三个对立面的数都分别相同的话就输出”Yes!”,否则输出”No!”。每个结果占一行,注意每50个结果要加一个空行。

样例输入

1
2
3
4
5
6
7
8
9
10
3
0 2 0 0
1 3 1 3
0 2 0 0
0 2 0 0
1 3 1 3
0 0 0 2
0 0 0 2
1 2 2 1
0 0 1 0

样例输出

1
2
3
Yes!
Yes!
No!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
int a[5]={0},T,x,m,Flag=0,n;

scanf("%d",&T);
rep(_,1,T+1){
Flag=0;
rep(i,0,4) {scanf("%d",&x);if(x) n=x;}
rep(i,0,4) scanf("%d",&a[i]);
rep(i,0,4) {scanf("%d",&x);if(x) m=x;}

if(a[1]!=a[3]||a[0]!=a[2]) Flag=1;
if(n!=m) Flag=1;

puts(Flag? "No!":"Yes!");
if(_%50==0) printf("\n");
}

return 0;
}


L.简单的分数

先通分,加减完再处以分子分母的最大公约数。

题目连接

描述

John最近对分数很感兴趣,在研究分数的加减运算。现在要求计算两个分数的运算。

输入

输入一个正整数T,表示有T组数据
每组数据包括5个整数op,a,b,c,d
op为1表示a/b + c/d;op为0表示为a/b – c/d
其中1 <= T, a,b,c,d <= 100;

输出

输出分数运算结果“x/y”,要求x/y是最简分数。

样例输入

1
2
3
4
5
4
1 1 2 1 3
0 1 2 1 2
1 1 2 1 2
0 1 3 1 2

样例输出

1
2
3
4
5/6
0/1
1/1
-1/6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
int n,op,a,b,c,d;
scanf("%d",&n);

rep(i,0,n){
scanf("%d%d%d%d%d",&op,&a,&b,&c,&d);
a*=d;c*=b;b*=d;d=b;

if(op) a+=c;
else a-=c;

int gcd=__gcd(a,b);
if(a<0||b<0) printf("-");
printf("%d/%d\n",abs(a/gcd),abs(b/gcd));

}
return 0;
}


M.HJ浇花

因为0 <= l <= r <= 10,所以可以直接差分。
用map存一下个数( map<次数,盆数> )。

题目连接

描述

HJ养了很多花(99999999999999999999999999999999999盆),并且喜欢把它们排成一排,编号0~99999999999999999999999999999999998,每天HJ都会给他的花浇水,但是他很奇怪,他会浇n(1 <= n <= 2 * 105)次水,每次都会选择一个区间[l, r],(0 <= l <= r <= 106),表示对区间[l, r]的花都浇一次水。现在问你,通过这些操作之后,被浇了i(1 <= i <= n)次水的花的盆数。

输入

输入:第一行一个n,表示HJ的操作次数,接下来的n行,表示每一次选择的浇水区间。

输出

输出:输出n个数字Cnt1, Cnt2……Cntn,(用空格隔开)Cnti表示被浇了i次水的花的盆数。

样例输入

1
2
3
4
5
6
7
8
3
0 3
1 3
3 8
3
1 3
2 4
5 7

样例输出

1
2
6 2 1
5 2 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=2e6+5;
int a[N]={0};
map<int,int> M;

int main()
{
int n,l,r,Max=0;
scanf("%d",&n);
rep(i,0,n){
scanf("%d%d",&l,&r);
a[l]++;
a[r+1]--;
if(r+1>Max) Max=r+1;
}
rep(i,1,Max+1) a[i]+=a[i-1];
rep(i,0,Max+1) M[a[i]]++;

map<int,int>::iterator iter=M.begin();
rep(i,1,n+1)
printf("%d%c",M[i]," \n"[i==n]);

return 0;
}

-------------本文结束 感谢您的阅读-------------

本文标题:西南民族大学第十届校赛(网络赛)题解

文章作者:Armin

发布时间:2018年12月31日 - 12:12

最后更新:2019年02月02日 - 19:02

原始链接:http://x-armin.com/西南民族大学第十届校赛(网络赛)题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波