普及T1 奖学金
按照题意排序即可。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct Stu{
int all, chi, id;
};
struct cmp{
inline bool operator()(const Stu& s1, const Stu& s2){
if(s1.all != s2.all)return s1.all > s2.all;
if(s1.chi != s2.chi)return s1.chi > s2.chi;
return s1.id < s2.id;
}
};
Stu s[505];
int n;
void init(){
n = read();
for(int i = 0; i < n; ++i)
s[i].id = i + 1,
s[i].all = s[i].chi = read(),
s[i].all += read() + read();
sort(s, s + n, cmp());
}
void solve(){
for(int i = 0; i < 5; ++i)
printf("%d %d\n", s[i].id, s[i].all);
}
int main(){
init();
solve();
return 0;
}
普及T2 纪念品分组
排序后大的尽量和小的组合，无法组合则直接退出。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int limit,n,k[30005],ans=0;
int main(){
scanf("%d%d",&limit,&n);
int i,at,o=0;
for(i=0;i<n;i++)scanf("%d",&k[i]);
std::sort(k,k+n);
for(i=0;i<n;i++){
for(o=0,at=n-1;at>i;at--)
if(k[at]<=limit-k[i]){o=1;break;}
if(o){ans+=n-at;n=at;}else{ans+=n-i;break;}
}printf("%d\n",ans);
return 0;
}
普及T3 守望者的逃离
方法一
分类讨论。。
尽量采取最优的策略。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
int m, s, t, ts, lim;
int get(){
if((10 - m) % 4)
return (10 - m) / 4 + 1;
return (10 - m) / 4;
}
int main(){
scanf("%d%d%d", &m, &s, &t);
for(int i = t, ts = s; i > 0; ){
if(ts <= 0) break;
if(m >= 10)
m -= 10, ts -= 60, i--;
else{
if(ts <= 17)
i--, ts=0;//跑一下就跑的到
else{
if((lim = get()) < 3){
if(i >= lim + 1){
if(ts <= 34){
i -= ts / 17;
if(ts % 17) i--;
ts = 0;//跑完全程
}else
i = i - (lim + 1), ts -= 60, m -= 10, m += lim * 4;
}else {
if(ts <= i * 17){
i -= ts / 17;
if(ts % 17) i--;
ts = 0;//跑完全程
}else
ts -= i * 17, i = 0;//尽量跑
}
}else{
if(i >= 7){
if(ts <= 7 * 17){
i -= ts / 17;
if(ts % 17) i--;
ts = 0;//跑完全程
}else
i -= 7, ts -= 120;
}else {
if(ts <= i * 17){
i -= ts / 17;
if(ts % 17) i--;
ts = 0;//跑完全程
}else
ts -= i * 17, i = 0;//尽量跑
}
}
}
}
if(ts > 0)
printf("No\n%d\n", s - ts);
else
printf("Yes\n%d\n", t - i);
return 0;
}
方法二
我们将法术和跑步分开来，跑一遍DP。
一开始只有法术，然后修改决策为跑步。
（来自洛谷上的神奇方法）
该方法之所以成立，就在于恢复完全是为了放出法术，而和跑步无关。因此可以将两者视为不同的决策。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int dp[300005];
void solve(){
int m = read(), s = read(), T = read();
dp[0] = 0;
for(int i = 1; i <= T; ++i){
if(m >= 10)
dp[i] = dp[i - 1] + 60, m -= 10;
else
dp[i] = dp[i - 1], m += 4;
}
for(int i = 1; i <= T; ++i){
dp[i] = max(dp[i], dp[i - 1] + 17);
if(dp[i] >= s){
printf("Yes\n%d\n", i);
break;
}
}
printf("No\n%d\n", dp[T]);
}
普及T4 Hanoi双塔问题
可以证明最短的次数一定是原汉诺塔问题的答案的两倍。
（因为最优情况下就是每一次要移动2个同样大小的盘子）
所以…加个高精度就完了。
提高T1 统计数字
模拟即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
int n,k[200005],tot=1,last;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&k[i]);
sort(k,k+n);
last=k[0];
for(int i=1;i<n;i++){
if(last!=k[i])
printf("%d %d\n",last,tot),tot=1,last=k[i];
else tot++;
}
printf("%d %d\n",last,tot);
return 0;
}