第一题。
M. B - Smartphone Addiction
问题描述
高桥的智能手机电池容量为NN毫安时。在时间0.50.5、1.51.5、2.52.5等时刻（即对于每个整数nn，时间为n + 0.5n+0.5），电池电量减少11毫安时。
高桥将在时间00带着充满电的手机离开家，去咖啡馆MM次，然后在时间TT回家。
他将在第ii个咖啡馆从时间A\_iA_i到时间B\_iB_i停留。在此期间，他会给手机充电，因此电池电量不会减少。相反，在每个整数nn的时间n + 0.5n+0.5，电量会增加11毫安时。然而，如果电量已经等于电池容量，它既不会增加也不会减少。
确定他是否能在回家的路上电池电量不降到00毫安时返回家。
限制条件
- 1 \le N \le 10^91≤N≤109
- 1 \le M \le 10001≤M≤1000
- 1 \le T \le 10^91≤T≤109
- 0 < A_1 < B\_1 < A\_2 < B\_2 < A\_3 < B\_3 < \dots < A\_M < B\_M < T0<A1<B_1<A_2<B_2<A_3<B_3<⋯<A_M<B_M<T
- 输入中的所有值都是整数。
输入
从标准输入以以下格式给出输入：
NN MM TT
A_1A1 B_1B1
A_2A2 B_2B2
A_3A3 B_3B3
\hspace{15pt} \vdots⋮
A_MAM B_MBM
输出
如果高桥能在回家的路上电池电量不降到00毫安时返回家，则打印Yes；否则，打印No。
示例输入 1
10 2 20
9 11
13 17
示例输出 1
Yes
电池电量变化如下：
- 时间00（离家）：1010毫安时
- 时间99（进入第一个咖啡馆）：11毫安时
- 时间1111（离开第一个咖啡馆）：33毫安时（他在咖啡馆给手机充电。）
- 时间1313（进入第二个咖啡馆）：11毫安时
- 时间1717（离开第二个咖啡馆）：55毫安时
- 时间2020（到家）：22毫安时
在此过程中，电池电量从未降到00毫安时，所以我们打印Yes。
示例输入 2
10 2 20
9 11
13 16
示例输出 2
No
这种情况与示例输入/输出1在他开始在第二个咖啡馆停留时的电量相同，为11毫安时。
当他在时间1616结束那里的停留时，电池电量为44毫安时。
然后在时间19.519.5，电量降至00，所以我们打印No。
示例输入 3
15 3 30
5 8
15 17
24 27
示例输出 3
Yes
电池电量在他到家时降至11毫安时，但在途中从未降到00毫安时。
示例输入 4
20 1 30
20 29
示例输出 4
No
电池电量在时间19.519.5降至00毫安时。
示例输入 5
20 1 30
1 10
示例输出 5
No
请注意，当电池电量等于电池容量时，停留在咖啡馆不会增加电池电量。
这道题其实求的就是在他走路的时候它的电量会减少。而在他去咖啡馆的时候，他的电量会增加。
然后呢我们用结构体去模拟就可以了
代码如下，
#include<bits/stdc++.h>
using namespace std;
struct Node {
int a,b;
}A[1010];
int n,m,t;
int main()
{
cin>>n>>m>>t;
int cnt=n;
for(int i=1;i<=m;i++) {
cin>>A[i].a>>A[i].b;
}
A[0].a=A[0].b=0;
A[m+1].a=A[m+1].b=t;
for(int i=0;i<=m;i++) {
int a1=A[i].b-A[i].a;
n+=a1;
n=min(n,cnt);
int a2=A[i+1].a-A[i].b;
n-=a2;
if(n<=0) {
cout<<"No";
return 0;
}
}
cout<<"Yes";
return 0;
}
第二题
N. C - ID (AI)
题目描述
在Atcoder共和国，有NN个县，总共有MM个城市属于这些县。
城市ii建立于年份Y_iYi，属于县P_iPi。
你可以假设在同一年没有建立多个城市。
决定为每个城市分配一个12位的ID号码。
如果城市ii是属于县ii的城市中建立的第xx个城市，那么城市ii的ID号码的前六位是P_iPi，最后六位是xx。
在这里，如果P_iPi或xx（或两者）少于六位数，则向左添加零，直到它有六位数。
找到所有城市的ID号码。
注意，可以有一个县没有城市。
约束条件
-
1 \leq N \leq 10^51≤N≤105
-
1 \leq M \leq 10^51≤M≤105
-
1 \leq P_i \leq N1≤Pi≤N
-
1 \leq Y_i \leq 10^91≤Yi≤109
-
Y_iYi都是不同的。
-
输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
NN MM
P_1P1 Y_1Y1
::
P_MPM Y_MYM
输出
按索引（城市11、城市22、...）的顺序打印所有城市的ID号码。
样例输入1
2 3
1 32
2 63
1 12
样例输出1
000001000002
000002000001
000001000001
-
由于城市11是县11中建立的第2个城市，其ID号码为000001000002000001000002。
-
由于城市22是县22中建立的第1个城市，其ID号码为000002000001000002000001。
-
由于城市33是县11中建立的第1个城市，其ID号码为000001000001000001000001。
样例输入2
2 3
2 55
2 77
2 99
样例输出2
000002000001
000002000002
000002000003
这道题主要运用到的方法就是结构体排序。
首先先排县
然后再排县中的城市。
最后再用一，把它们依次输出来。
代码如下
#include<bits/stdc++.h>
using namespace std;
struct Node {
int p,y,id,pm;
}A[101000];
bool a11(Node u,Node v)
{
return(u.p<v.p||u.p==v.p&&u.y<v.y) ;
}
bool a22(Node u,Node v)
{
return u.id<v.id;
}
int n,m,x=1;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>A[i].p>>A[i].y;
A[i].id=i;
}
sort(A+1,A+m+1,a11);
A[1].pm=x;
for(int i=2;i<=m;i++)
{
if(A[i].p==A[i-1].p)
{
x++;
A[i].pm=x;
}
else
{
x=1;
A[i].pm=x;
}
}
sort(A+1,A+1+m,a22);
for(int i=1;i<=m;i++)
{
printf("%06d%06d\n",A[i].p,A[i].pm);
}
return 0;
}
