出来挨揍了哈哈哈哈哈哈哈哈哈哈哈
这次跟飞哥出题的主旨呢(其实并没有什么主旨)就是把难度梯度分开一些，让大家充分感受到ACM校赛的亲切感(你信吗？反正我是不信)。
总得来讲我们把七道题目(先除去可爱的签到题嘤嘤嘤)分成了三个档次，一个是ACM选手能较轻松过完，外来选手们能够得到锻炼的题目，B题C题就是这一个档次的题目，不过首先来说一下A题
A题(签到题)
题目传送门:https://ac.2333.moe/Problem/view.xhtml?id=1616
如假包换的签到题！
电子竞技不需要数数！
为什么提问题的那个ACM也要算进去呢！
因为爱情啊！
1
2
3
4
5
6
7
| #include <iostream>
using namespace std;
int main(){
cout << "12" << endl;
return 0;
}
|
B题(哈希计数)
题目链接:http://bailian.openjudge.cn/practice/4002/
这道题只需要开一个数组作为计数器就可以搞定。
我们只需要对书开一个数组，每次有一个人喜欢这本书就+1，最后输出的时候查询某个人喜欢的书的值-1就是答案(-1是为了把自己减掉)
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
| #include <iostream>
#include <cstring>
using namespace std;
const int maxn=300;
int a[maxn],s[maxn];
int main(){
int n,m;
ios::sync_with_stdio(false);
while(cin>>n>>m){
memset(a,0,sizeof(a));
memset(s,0,sizeof(s));
for(int i=0;i<n;i++){
cin>>a[i];
s[a[i]]++;
}
for(int i=0;i<n;i++)
if(s[a[i]]-1)
cout << s[a[i]]-1 << endl;
else
cout << "BeiJu" << endl;
}
return 0;
}
|
C题(字符串)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1106
这题比A题和B题略难一些，主要就是我自己WA了一发(哈哈哈，尴尬)，没有注意到整个字符串都没有5的情况，还有就是连续都是5的情况，只要及时冷静地发现这两个坑点这个题就很好过
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
| #include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=1010;
int main(){
string s;
int a[maxn];
vector<int> ans;
while(cin>>s){
ans.clear();
memset(a,0,sizeof(a));
int sum=0,flag=0;
for(int i=0;i<s.length();i++){
if(s[i]=='5') {
if(flag)
ans.push_back(sum);
sum = 0;
flag=0;
}
else {
flag=1;
sum *= 10;
sum += s[i] - '0';
}
if(i==s.length()-1&&s[i]!='5')
ans.push_back(sum);
}
sort(ans.begin(),ans.end());
for(auto it=ans.begin();it!=ans.end();it++){
if(it!=ans.begin()) cout << ' ';
cout << *it;
}
cout << endl;
}
return 0;
}
|
D题(优先队列)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1873
作为一个阴险的出题人，当然不能出裸的优先队列啦，不能变成打字比赛啊(雾)
所以这道题的优先队列有两个优先级，一个是看病的优先级，还有一个就是时间的优先级，所以显而易见需要重载运算符了，注意点就是优先队列重载运算符刚好是反一下的，大于就是小于，小于就是大于，如果你熟练掌握了优先队列的话这题过的比上一题快多了
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
| #include <iostream>
#include <queue>
using namespace std;
int n;
struct node{
int x,y;
friend bool operator < (node a,node b){
return a.x==b.x?a.y>b.y:a.x<b.x;
}
node(int x,int y){
this->x=x;
this->y=y;
}
};
int main(){
while(cin>>n){
string s;int a,b,c=0;
priority_queue<node> que[3];
while(n--) {
cin >> s;
if (s == "IN") {
c++;
cin >> a >> b;
que[a - 1].push(node(b, c));
} else {
cin >> a;
if (!que[a - 1].empty()) {
node p = que[a - 1].top();
que[a - 1].pop();
cout << p.y << endl;
} else
cout << "EMPTY" << endl;
}
}
}
return 0;
}
|
E题(最短路径)
题目链接:http://poj.org/problem?id=2387
读题！读题！读题！
重要的事情说三遍！
边数和点数的输入是反的，除了这个致命的坑点之外这就是一道最短路径的裸题
用SPFA或者迪杰斯特拉都是可以过的，应该不会有大佬头铁去跑Floyd吧(呵呵哒)
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
| #include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=1010;
struct node{
int x,y;
bool operator < (const node& a) const{
return x>a.x;
}
node(int x,int y){
this->x=x;
this->y=y;
};
};
int map[maxn][maxn];
int d[maxn];
int main(){
int n,m;
ios::sync_with_stdio(false);
while(cin>>m>>n){
for(int i=1;i<=n;i++)
d[i]=(int)1e9;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=i==j?0:(int)1e9;
int a,b,val;
for(int i=0;i<m;i++){
cin>>a>>b>>val;
map[a][b]=min(map[a][b],val);
map[b][a]=min(map[b][a],val);
}
priority_queue<node> que;
d[1]=0;
que.push(node(d[1],1));
while(!que.empty()){
int u=que.top().y;que.pop();
for(int v=1;v<=n;v++){
if(map[u][v]!=(int)1e9&&v!=u) {
if (d[v] > d[u] + map[u][v]) {
d[v] = d[u] + map[u][v];
que.push(node(d[v], v));
}
}
}
}
cout << d[n] << endl;
}
return 0;
}
|
F题(动态规划)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084
这道虽说是DP题，可是这个DP其实非常简单(不要被DP这个名字吓死就行)，既然求最顶端下来的最小值，我们直接从底端开始反推(除非你非要从顶端开始做这题，那就递归吧，又浪费空间又浪费脑子)
我这个代码是从倒数第二层开始推出来的公式，核心就是这个公式
a[i][j]=max(a[i+1][j],a[i+1][j+1])
没错，你弄懂了这个这个代码比杨辉三角都简单(逃)，做不出来可是要谢罪的
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[120][120];
int m,n;
int main()
{
cin >> m;
while(m--){
memset(a,0,sizeof(a));
cin >> n;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
cin >> a[i][j];
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
if(a[i+1][j]>a[i+1][j+1])
a[i][j]+=a[i+1][j];
else
a[i][j]+=a[i+1][j+1];
}
}
cout << a[0][0] << endl;
}
return 0;
}
|
G题(组合数学+快速幂)
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1008
这道题代码量并不多，为什么放在比较难的题目里呢，因为需要让脑筋来个急转弯
相同的状态数及其不好求简直要命，那么既然是状态数的问题，首先我们可以想到m^n是所有状态，我们只要拿所有的状态数减去不可能发生越狱的状态数就可以得出可能越狱的状态数了，想到这一点这道题就很简单了
那么不可能越狱的状态有多少种呢？首先第一个人可以信仰m种宗教，然后他旁边的人就只能信仰m-1种了，然后再旁边的还是m-1种(这个别搞混了，因为第三个人完全可以信仰第一个人信仰的宗教)，仔细思考一下后面所有的人其实都是m-1种(这个不解释了，比较明显了)，所以不可能越狱的状态共有(m-1)^(n-1)*m种
所以最后的答案是m^n-(m-1)^(n-1)*m种，那么我们计算(m-1)^(n-1)时由于n-1太大了，所以需要进行快速幂，快速幂这里就不详细解释了，套模板就行，但是还有一个注意点就是在快速幂函数中与后面求答案的时候都需要在每次取模
最后一个难题的坑点在于m^n减去(m-1)^(n-1)*m的时候，由于这两位都是被取模过的，所以会减出负数，所以需要对最后的答案加上mod再取模一次才可以AC
这是一道考验组合数学与快速幂以及数学功底的题目(逃)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <iostream>
using namespace std;
const int mod=100003;
long long pow_mod(long long a,long long i,long long n){
if(i==0)
return 1%n;
long long t=pow_mod(a,i>>1,n);
t=t*t%n;
if(i&1) t=t*a%n;
return t;
}
int main(){
long long n,m;
while(cin>>m>>n){
long long ans=(pow_mod(m,n,mod)-(m*pow_mod(m-1,n-1,mod))%mod+mod)%mod;
cout << ans << endl;
}
return 0;
}
|
H题(魔改线段树)
题目链接:http://hihocoder.com/problemset/problem/1665
其实从周三前我线段树安排的一直就是一道裸题（就是裸的不能再裸的那种），出题的尴尬境地就在于出难了时间不够做不出来，出太裸的题就一顿套模板xjbAC毫无体验
经过我翻遍了无数oj的线段树题，终于在hihoCoder这个我平时都不刷的平台找到一道有意思的线段树题目，由于我的AC方式过于魔性所以我将其称为魔改线段树(啊哈哈)
题目就不赘述了，这道题需要把线段树魔改成什么样子捏？
众所周知线段树按功能分可以粗糙地分为两种，求和的与求区间最值的，这道题当有新的木块放上去的时候我们可以看成是查询要被覆盖的区间[l,r]的最值，假设值为ans，然后我们将ans+1作为区间[l,r]的新的值更新上去，然后对所有的[l,r]询问都这么做就行了
所以这个问题就变成了——将一个区间更新的线段树的update函数功能改成修改区间值，将query函数功能改成区间查询最大值，这就造出了一个”四不像线段树”，但是我能过题你气不气？
所以下面就是我AC的魔改线段树(因为这题网上查不到别人写的题解，我至今也不知道我这个是不是正规套路，所以暂且就叫魔改线段树吧)
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
using namespace std;
const int maxn=100010;
struct node{
int l,r;
int sum,lazy;
void update(int val){
sum=val;
lazy=val;
}
}tree[4*maxn];
struct Q{
int l,r;
}q[maxn];
void push_up(int x){
tree[x].sum=max(tree[x<<1].sum,tree[(x<<1)|1].sum);
}
void push_down(int x){
int val=tree[x].lazy;
if(val){
tree[x<<1].update(val);
tree[(x<<1)|1].update(val);
tree[x].lazy=0;
}
}
void build(int x,int l,int r){
tree[x].l=l,tree[x].r=r,tree[x].lazy=0;
if(l==r)
tree[x].sum=0;
else{
int mid=(l+r)/2;
build(x<<1,l,mid);
build((x<<1)|1,mid+1,r);
push_up(x);
}
}
void update(int x,int l,int r,int val){
int L=tree[x].l,R=tree[x].r;
if(l<=L&&R<=r)
tree[x].update(val);
else{
push_down(x);
int mid=(L+R)/2;
if(l<=mid) update(x<<1,l,r,val);
if(r>mid) update((x<<1)|1,l,r,val);
push_up(x);
}
}
int query(int x,int l,int r){
int L=tree[x].l,R=tree[x].r;
if(l<=L&&R<=r)
return tree[x].sum;
else{
int sum=0;
push_down(x);
int mid=(L+R)/2;
if(l<=mid) sum=max(sum,query(x<<1,l,r));
if(r>mid) sum=max(sum,query((x<<1)|1,l,r));
push_up(x);
return sum;
}
}
int main(){
ios::sync_with_stdio(false);
int n;
while(cin>>n){
memset(q,0,sizeof(q));
memset(tree,0,sizeof(tree));
int mx=0;
for(int i=1;i<=n;i++){
cin>>q[i].l>>q[i].r;
mx=max(mx,q[i].r);
}
build(1,1,mx);
for(int i=1;i<=n;i++) {
int ans=query(1, q[i].l, q[i].r)+1;
cout << ans << endl;
update(1, q[i].l, q[i].r, ans);
}
}
return 0;
}
|