A : 小明上学
题目背景
小明是汉东省政法大学附属中学的一名学生，他每天都要骑自行车往返于家和学校。为了能尽可能充足地睡眠，他希望能够预计自己上学所需要的时间。他上学需要经过数段道路，相邻两段道路之间设有至多一盏红绿灯。
京州市的红绿灯是这样工作的：每盏红绿灯有红、黄、绿三盏灯和一个能够显示倒计时的显示牌。假设红绿灯被设定为红灯 rr 秒，黄灯 yy 秒，绿灯 gg 秒，那么从 00 时刻起，[0,r)[0,r) 秒内亮红灯，车辆不许通过；[r, r+g)[r,r+g) 秒内亮绿灯，车辆允许通过；[r+g, r+g+y)[r+g,r+g+y) 秒内亮黄灯，车辆不许通过，然后依次循环。倒计时的显示牌上显示的数字 l(l > 0)l(l>0)是指距离下一次信号灯变化的秒数。
问题描述
一次上学的路上，小明记录下了经过每段路的时间，和各个红绿灯在小明到达路口时的颜色和倒计时秒数。希望你帮忙计算此次小明上学所用的时间。
输入格式
输入的第一行包含空格分隔的三个正整数 rr、yy、gg，表示红绿灯的设置。这三个数均不超过 10^610 6。
输入的第二行包含一个正整数 n(n \leq 100)n(n≤100)，表示小明总共经过的道路段数和看到的红绿灯数目。
接下来的 n 行，每行包含空格分隔的两个整数k、t。k=0 表示经过了一段道路，耗时 t 秒，此处 t 不超过 10^610 6 ；k=1、2、3 时，分别表示看到了一个红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 t，此处 t 分别不会超过 r、y、g。
输出格式
输出一个数字，表示此次小明上学所用的时间。
样例输入
30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3
样例输出
70
样例说明
小明先经过第一段道路，用时 1010 秒，然后等待 55 秒的红灯，再经过第二段道路，用时 1111 秒，然后等待 22 秒的黄灯和 3030 秒的红灯，再经过第三段、第四段道路，分别用时66、33秒，然后通过绿灯，再经过最后一段道路，用时 33 秒。共计 10 + 5 + 11 + 2 + 30 + 6 + 3 + 3=7010+5+11+2+30+6+3+3=70 秒。
评测用例规模与约定
测试点 1, 2 中不存在任何信号灯。
测试点 3, 4 中所有的信号灯在被观察时均为绿灯。
测试点 5, 6 中所有的信号灯在被观察时均为红灯。
测试点 7, 8 中所有的信号灯在被观察时均为黄灯。
测试点 9, 10 中将出现各种可能的情况。
#include<iostream>
using namespace std;
int main()
{int n;
int r,y,g;
cin>>r>>y>>g;
cin>>n;
int ans=0;
int k,t;
while(n--)
{
cin>>k>>t;
if(k==0)
ans+=t;
else if(k==1)
ans+=t;
else if(k==2)
ans+=t+r;
}
cout<<ans<<endl;
}
B : 小中大
题目背景
在数据分析中，最小值最大值以及中位数是常用的统计信息。
题目描述
老师给了你 nn 个整数组成的测量数据，不保证有序，可能存在重复的数据。请统计出这组测量数据中的最大值、中位数以及最小值，并按照从大到小的顺序输出这三个数。
输入格式
从标准输入读入数据。
第一行输入一个整数 nn，在第二行中存在 nn 个整数，表示测量数据，可能存在多个整数相等，整数与整数之间使用空格隔开。
输出格式
输出到标准输出。
包含一行，包括最大值、中位数以及最小值共三个数，并按照从大到小的顺序输出。数据与数据之间使用空格隔开。对于整数请直接输出整数，对于可能出现的分数，请输出四舍五入保留 11 位小数的结果。
样例1输入
3
-1 2 4
样例1输出
4 2 -1
样例1解释
44 为最大值，22 为中位数，-1−1 为最小值。
样例2输入
4
-2 -1 3 4
样例2输出
4 1 -2
样例2解释
44 为最大值，(-1+3)÷2=1(−1+3)÷2=1 为中位数，-2−2为最小值。
子任务
#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
int main()
{
int n;
std::vector<int> v;
double cen;
bool teil = false;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int a;
scanf("%d", &a);
v.push_back(a);
}
std::sort(v.begin(), v.end());
if (v.size() % 2 == 1)
{
cen = v[v.size() / 2];
}
else
{
cen = v[v.size() / 2] + v[v.size() / 2 - 1];
cen /= 2;
if (cen - (int)(cen) != 0)
{
teil = true;
}
}
if (teil)
{
printf("%d %.1f %d\n", v.back(), cen, v.front());
}
else
{
printf("%d %.0f %d\n", v.back(), cen, v.front());
}
return 0;
}
C : 树状数组
题目描述
给定数列 a_1, a_2, \dots, a_na
1 ,a 2 ,…,a n
，你需要依次进行 qq 个操作，操作有两类：
1 i x：给定 i,xi,x，将 a_ia i 加上 xx；
2 l r：给定 l,rl,r，求 \sum_{i=l}^r a_i∑
i=lr a i 的值（换言之，求 a_l+a_{l+1}+\dots+a_ra l +a l+1 +⋯+a r 的值）。
输入格式
第一行包含 22 个正整数 n,qn,q，表示数列长度和询问个数。保证 1\le n,q\le 10^61≤n,q≤10 6 。
第二行 nn 个整数 a_1, a_2, \dots, a_na
1 ,a 2 ,…,a n ，表示初始数列。保证 |a_i|\le 10^6∣a i ∣≤10 6 。
接下来 qq 行，每行一个操作，为以下两种之一：
1 i x：给定 i,xi,x，将 a[i]a[i] 加上 xx；
2 l r：给定 l,rl,r，求 \sum_{i=l}^r a_i∑
i=lr a i 的值。
保证 1\leq l\leq r\leq n,1≤l≤r≤n, |x|\le 10^6∣x∣≤10 6
。
输出格式
对于每个 2 l r 操作输出一行，每行有一个整数，表示所求的结果。
样例
输入样例
3 2
1 2 3
1 2 0
2 1 3
输出样例
6
数据范围
对于所有数据，1\le n,q\le 10^6,1≤n,q≤10 6 , |a_i|\le 10^6∣a i ∣≤10 6 , 1\le l\le r\le n,1≤l≤r≤n, |x|\le 10^6∣x∣≤10 6 。
#include <iostream>
#include <cstdio>
typedef long long un;
un tree[9999999];
un lowbit(un x)
{
return x & (-x);
}
void update(un x, un diff, un size)
{
for (un i = x; i < size; i += lowbit(i))
{
tree[i] += diff;
}
}
un sumof(un x)
{
un sum = 0;
for (un i = x; i; i -= lowbit(i))
{
sum += tree[i];
}
return sum;
}
int main()
{
un size;
un ops;
scanf("%lld %lld", &size, &ops);
size++;
for (un i = 1; i < size; i++)
{
un a;
scanf("%lld", &a);
update(i, a, size);
}
for (un i = 0; i < ops; i++)
{
int cmd;
un a, b;
scanf("%d %lld %lld", &cmd, &a, &b);
if (cmd == 1)
{
update(a, b, size);
}
else
{
printf("%lld\n", sumof(b) - sumof(a - 1));
}
}
return 0;
}
D : 排名
题目描述
sys 参加了一场 AI 算法大赛，大赛要求参赛者提供一个程序，后台的评测系统会使用相同的数据对所有提交程序进行评测，通过程序的运行时间与内存占用来衡量一个算法的好坏。
比赛的成绩计算方法为，给每一个程序进行打分，对于一个程序来说，该程序的得分为：运行时间与内存占用均小于等于该程序的程序的数量。
现在需要你来计算，成绩为 0,1,\dots n-10,1,…n−1 的程序的数量分别为多少。
输入格式
第一行一个整数 NN，表示程序的数目；
接下来 NN 行给出每个程序的运行时间与内存占用，用两个空格隔开的整数表示；
不会有两个程序的运行时间与内存占用均相同。
输出格式
nn 行，每行一个整数，分别是得分为 00，11，22，\dots…，n-1n−1 的程序的数目。
样例
输入
5
1 1
5 1
7 1
3 3
5 5
输出
1
2
1
1
0
数据范围
对于全部数据，1\le n\le 10^61≤n≤10
6
，0\le 运行时间,内存占用 \le 10^60≤运行时间,内存占用≤10
6
。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[2000010],s[2000010];
ll lb(ll x)
{
return x&(-x);
}
ll ask(ll x)
{
ll res=0;
for(int i=x;i>=1;i-=lb(i)) res+=s[i];
return res;
}
void upd(ll x,ll v)
{
for(ll i=x;i<=2000010;i+=lb(i)) s[i]+=v;
}
struct node
{
ll tim;ll use;
node(int a,int b){tim=a,use=b;}
bool operator < (const node &A)const{
return tim<A.tim||(tim==A.tim&&use<A.use);
}
};
int main()
{
scanf("%lld",&n);
vector<node> g;
for(ll i=0;i<n;i++)
{
ll b,c;scanf("%lld%lld",&b,&c);
c++,b++;
node t(b,c);
g.push_back(t);
}
sort(g.begin(),g.end());
for(ll i=0;i<g.size();i++)
{
a[ask(g[i].use)]++;
upd(g[i].use,1);
}
for(ll i=0;i<n;i++)
{
cout<<a[i]<<'\n';
}
return 0;
}
E : 火星饭店
题目描述
lzh 在火星开了一家饭店，为了吸引顾客，饭店会不定期在菜谱中加入新菜，每个菜都有一个美味度 l(0\le l < p)l(0≤l<p)。
饭店使用手机进行点餐，手机上展示的菜谱会按照更新的顺序逆序排列。由于不同顾客的手机屏幕分辨率大小不同，所以能够显示在第一屏的菜谱的数量也不同。根据调查发现，火星用户只会在第一屏的菜品中选择美味度最高的购买。
现在按照时间顺序输入 mm 个添加菜品或顾客点菜的操作，请输出每位点菜顾客所点的菜的美味度。
输入格式
第一行有两个正整数 m,pm,p，意义如题目描述；
接下来 mm 行，每一行表示一个操作。
如果该行的内容是 Q L，则表示有顾客进行了点菜，该顾客的手机屏幕可以显示 LL 个菜品；
如果是 A t，则表示加入了新的菜品，菜品的美味度是 (t+a)\bmod p(t+a)modp。
tt 是输入的参数
aa 是在这个添加操作之前最后一个点菜操作的答案（如果之前没有点菜操作，则 a = 0a=0）。
数据保证第一个操作一定是添加菜品。在顾客点菜时，L\gt 0L>0 且不超过当前已有菜品的数量。
输出格式
对于每一个点菜操作，输出一行。该行只有一个数，即当前屏幕中美味度最大的菜品的美味度。
样例
输入
10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99
输出
97
97
97
60
60
97
数据范围
对于全部数据，1\le m\le 2\times 10^5,1\le p\le 2\times 10^9,0\le t\lt p1≤m≤2×10
5
,1≤p≤2×10
9
,0≤t<p。
#include <iostream>
#include <cstdio>
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a > b ? b : a)
typedef long long un;
un tree[9999999];
un tsize = 0;
un mr = 0;
void update(un pos, un value, un base = 1, un l = 1, un r = -1)
{
if (r == -1) r = mr;
if (l == r)
{
tree[base] += value;
return;
}
un mid = (l + r) / 2;
if (pos <= mid)
update(pos, value, base * 2, l, mid);
else
update(pos, value, base * 2 + 1, mid + 1, r);
tree[base] = MAX(tree[base * 2], tree[base * 2 + 1]);
}
un maxof(un pl, un pr, un base = 1, un l = 1, un r = -1)
{
r = (r == -1 ? mr : r);
if (pl == l && pr == r) return tree[base];
un mid = (l + r) / 2;
if (pr <= mid)
return maxof(pl, pr, base * 2, l, mid);
else if (pl > mid)
return maxof(pl, pr, base * 2 + 1, mid + 1, r);
else
{
return MAX(
maxof(pl, mid, base * 2, l, mid),
maxof(mid + 1, pr, base * 2 + 1, mid + 1, r));
}
}
int main()
{
un m, p;
un qa = 0;
tsize = 1;
scanf("%lld %lld", &m, &p);
mr = m;
for (un i = 0; i < m; i++)
{
char c[4];
scanf("%s", c);
if (c[0] == 'Q')
{
un l;
scanf("%lld", &l);
qa = maxof(tsize - l, tsize - 1);
printf("%lld\n", qa);
/*for (int i = 0; i < mr * 4; i++)
{
printf("%lld ", tree[i]);
}
printf("\n");*/
}
else
{
un u;
scanf("%lld", &u);
u = (u + qa) % p;
update(tsize, u);
tsize++;
}
}
return 0;
}
思路
A小明上学
每次判断当前的灯的颜色（k的值），如果k是0或3,则无需等待，通过道路，加上对应时间；如果k是1，则需要等待红灯时间，之后通过；如果k是2，则需等待黄灯、红灯时间，之后通过；累加时间输出即可。
B小中大
输入到数组中，之后对数组进行sort；
之后判断中位数的位置（是否需要两个相加除二），判断是否需要保留一位小数；
最后输出最后一个元素、中位数、第一个元素即可。
C树状数组
通过差分的思想；维护tree数组
对于给定 i,x，将 ai 加上 x操作：
将i到最后的元素都加上x
对于第二个操作 求l到r的和：
用前r项和减去前l-1项的和即可。
D 排名
构造结构体储存每个程序的运行时间、内存占用；
重载比较函数，用vector结构体数组存储输入，sort；
之后记录数目输出即可。
E
通过数组记录包括本项及之前所有的最大值；
即a[i]表示前i项中的最大值；
每次插入新菜则更新a[i]；
顾客点菜则根据手机屏幕大小输出对应的最大值即可。