比赛链接

A:

思路:如何在最小的次数配成浓度恰为K%的药水,很明显100/gcd(100,k)即可。

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;
typedef long long ll;
const ll maxn=1e5+7;
const ll mod = 1e9+7;
int _,n,m;
int main()
{
for(cin>>_;_;_--)
{

cin>>n;
cout<<100/(__gcd(100,n))<<endl;

}

return 0;
}

B:

思路:因为不能选全部,所以每次都可以贪心的选n-1个,那么也就是第一个和第n个元素比较特殊,所以当a[1]=1或者a[n]=n时输出1,当a[1]=n且a[n]=1时输出3,其他除了已经有序的情况都是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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+7;
const ll mod = 1e9+7;
int _,n,m;
int a[maxn];
int main()
{
for(cin>>_;_;_--)
{
cin>>n;
bool f=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==i)
{
continue;
}
else
{
f=0;
}
}
if(f)//本身有序
{
cout<<0<<endl;
}
else if(a[1]==1||a[n]==n)
{
cout<<1<<endl;
}
else if(a[1]==n && a[n]==1)
{
cout<<3<<endl;
}
else
{
cout<<2<<endl;
}
}

return 0;
}


C:

思路:第一,可以证明只有同一时刻(初始时刻)位置奇偶性相同的球是可以相消的
第二,对于任意两个球方向有四种情况(左左,左右,右左,右右)。
第三,对于上面四种情况,右左最先消除,左左,右右并列第二消除,左右最后消除。
所以就是简单的括号匹配了。
先按初始时刻位置大小从小到大排序,然后用双端队列(消除左右,右右时候用队尾,消除左左的时候用队首)维护就好了。
注意奇偶性相同才可以消除就写出来。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=3e5+7;
const ll mod = 1e9+7;
int _,n,m;
int q,w;
deque<ll > lj,lo,rj,ro;
ll ans[maxn];
struct kkk{
ll val;
char p;
int num;
}node [maxn];
bool cmp(kkk a,kkk b)
{
return a.val<b.val;
}
void init()
{
while(!lj.empty()){
lj.pop_back();}
while(!rj.empty()){
rj.pop_back();}
while(!lo.empty()){
lo.pop_back();}
while(!ro.empty()){
ro.pop_back();}

}
int main()
{
for(cin>>_;_;_--)
{
init();
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>node[i].val;
node[i].num=i;
ans[i]=-1;
}
for(int i=1;i<=n;i++)
{
cin>>node[i].p;
}

sort(node+1,node+n+1,cmp);
//print();
//情况一
for(int i=1;i<=n;i++)
{
//cout<<node[i].val<<"\n";
if(node[i].val&1)//奇数
{
if(node[i].p=='L')
{
lj.push_back(i);
if(!rj.empty())
{
q=lj.back();
w=rj.back();
lj.pop_back();
rj.pop_back();
ans[node[q].num] = abs(node[q].val-node[w].val)/2;
ans[node[w].num] = abs(node[q].val-node[w].val)/2;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}
}
else
{
rj.push_back(i);
}
}
else
{
if(node[i].p=='L')
{
lo.push_back(i);
if(!ro.empty())
{
q=lo.back();
w=ro.back();
lo.pop_back();
ro.pop_back();
ans[node[q].num] = abs(node[q].val-node[w].val)/2;
ans[node[w].num] = abs(node[q].val-node[w].val)/2;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}
}
else
{
ro.push_back(i);
}
}
}

// print2();
//情况二
while(!lj.empty())
{
if(lj.size()==1)
{
break;
}
q=lj.front();
lj.pop_front();
w=lj.front();
lj.pop_front();
ans[node[q].num]= abs(0-node[q].val+0-node[w].val)/2;
ans[node[w].num]= abs(0-node[q].val+0-node[w].val)/2;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";

}

while(!lo.empty())
{
if(lo.size()==1)
{
break;
}
q=lo.front();
lo.pop_front();
w=lo.front();
lo.pop_front();
ans[node[q].num]= abs(0-node[q].val+0-node[w].val)/2;
ans[node[w].num]= abs(0-node[q].val+0-node[w].val)/2;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";

}
while(!rj.empty())
{
if(rj.size()==1)
{
break;
}
q=rj.back();
rj.pop_back();
w=rj.back();
rj.pop_back();
ans[node[q].num]= abs(m-node[q].val+m-node[w].val)/2;
ans[node[w].num]= abs(m-node[q].val+m-node[w].val)/2;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}


while(!ro.empty())
{
if(ro.size()==1)
{
break;
}
q=ro.back();
ro.pop_back();
w=ro.back();
ro.pop_back();
ans[node[q].num]= abs(m-node[q].val+m-node[w].val)/2;
ans[node[w].num]= abs(m-node[q].val+m-node[w].val)/2;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}



while((!lo.empty())&&(!ro.empty()))
{
q=lo.front();
lo.pop_front();
w=ro.back();
ro.pop_back();
//考虑一下
if(m-node[w].val>=node[q].val)
{
int temp=m-node[w].val;
node[w].val=m;
node[q].val=temp-node[q].val;
ans[node[q].num] = abs(node[q].val-node[w].val)/2+temp;
ans[node[w].num] = abs(node[q].val-node[w].val)/2+temp;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}
else
{
int temp=node[q].val;
node[w].val=m-(temp-(m-node[w].val));
node[q].val=0;
ans[node[q].num] = abs(node[q].val-node[w].val)/2+temp;
ans[node[w].num] = abs(node[q].val-node[w].val)/2+temp;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}
//int temp = max(m-node[w].val,node[q].val);



}
while((!lj.empty())&&(!rj.empty()))
{
q=lj.front();
lj.pop_front();
w=rj.back();
rj.pop_back();
//考虑一下
if(m-node[w].val>=node[q].val)
{
int temp=m-node[w].val;
node[w].val=m;
node[q].val=temp-node[q].val;
ans[node[q].num] = abs(node[q].val-node[w].val)/2+temp;
ans[node[w].num] = abs(node[q].val-node[w].val)/2+temp;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}
else
{
int temp=node[q].val;
node[w].val=m-(temp-(m-node[w].val));
node[q].val=0;
ans[node[q].num] = abs(node[q].val-node[w].val)/2+temp;
ans[node[w].num] = abs(node[q].val-node[w].val)/2+temp;
//cout<<node[q].num<<" "<<node[w].num<<" "<<ans[node[w].num]<<"\n";
}
//int temp = max(m-node[w].val,node[q].val);
}

//cout<<"ans"<<"\n";
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";


}
return 0;
}

D:

思路: 一开始对椅子分类分为有人坐和没人坐的椅子,对于第i个最初没有人的椅子,它一定是被第1-i个人去坐,当然也存在不被人坐的情况,不可能被后面的人坐,后者会有前i个人中的某一个去了后面的座位使得路程重复。如此一来枚举每个没有人的椅子就OK了。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=5005;
const ll mod = 1e9+7;
int _,n,m;
int a[maxn];
int use[maxn];
int notuse[maxn];
int cnt,cnt2;
ll dp[maxn];
int f[maxn];
int b[maxn],c[maxn];
int main()
{
cin >> n;
int cb = 0, cc = 0;
for (int i = 1, te; i <= n; ++i) {
cin >> te;
if(te)
{
b[++cb]=i;
}
else
{
c[++cc]=i;
}
}
for(int i=1;i<5005;i++)
{
f[i]=mod;
}
for (int i = 1; i <= cc; i++)
{
for (int j = 1; j <= min(cb,i); j++)
{
f[j] = min(f[j], f[j - 1] + abs(b[j] - c[i]) );
}
}
cout << f[cb] << "\n";
}

写在最后:
某些菜狗已经打了一年半了,打的依旧是Speedforces。