Educational Round 146 (Rated for div 2)
Educational Codeforces Round 146 (Rated for Div. 2)
$A$
比较简单，给定 $k,n$,判断 $2x+ky=n$ 可不可行
直接$\gcd$裴蜀定理搞完了，有的人写了 exoj，鉴定为蠢
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
int T;
int n,k;
inline int read(){
int s=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*f;
}
inline void write(int x){
int top=0,sta[35];
while(x) {sta[top++]=x%10,x/=10;}
while(top) {putchar(sta[--top]+'0');}
}
inline int exgcd(int a,int b,int& x,int& y)
{
if (!b)
{
x=1;y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int z=x;x=y,y=z-(a/b)*y;
return d;
}
int main()
{
T=read();
while (T--)
{
n=read(),k=read();
int x=0,y=0;int gcd=exgcd(2,k,x,y);
if (n%gcd) puts("NO");
else puts("YES");
}
return 0;
}
|
$B$
题意：给定终点 $(x,y)$ ，机器人有一个腿长 $m$，每次可以选择走到 $(x+m,y)$ 或 $(x,y+m)$ 或者是$m$加上 $1$。求到达 $(x,y)$ 的最小步数
为啥感觉比 $C$ 难
考虑腿长为 $m$ 时，充能需要 $m-1$ 秒，从 $(0,0)$ 到 $(x,y)$ 的最小步数为 $m-1+\lceil \frac {x} {m} \rceil + \lceil \frac {y} {m} \rceil$
证明：定义 $k_1=x \bmod m$，如果 $k_1=0$，则刚好到。否则则在 $m=k_1$ 时在 $x$ 方向走 $1$ 次（刚好表示为向上取整）。$y$ 方向同理。
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
int T;
int n,m;
inline int read(){
int s=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*f;
}
inline void write(int x){
int top=0,sta[35];
while(x) {sta[top++]=x%10,x/=10;}
while(top) {putchar(sta[--top]+'0');}
}
int main()
{
T=read();
while (T--)
{
int ans=1e9;
n=read(),m=read();
for (int i=1;i<=50000;i++)
{
int res=i-1;
res+=(n%i?n/i+1:n/i);
res+=(m%i?m/i+1:m/i);
ans=min(ans,res);
}
printf("%d\n",ans);
}
return 0;
}
|
$C$
题意：两个机器人，构造两个数组，表示每个机器人会轮着去的箱子。箱子里有这个箱子颜色的球，要求 $1\dots n$ 种颜色各有 $r_i$ 个。每个机器人扫箱子分别需要$s_1,s_2$秒，构造数组使得要求被满足的时间最少。
比较容易想到的是，既然 $r_i$ 出现的次数要多，显然需要把 $r_i$ 更大的排在前面。给所有 $2n$ 个位置排序，取前 $n$ 个位置从大到小放置 $r_i$ 即可
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct Node{
int s,pos;
bool operator < (const Node& rhs) const{
return s<rhs.s;
}
};
int T,n,s1,s2;
int r[N],id[N];
inline int read(){
int s=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*f;
}
inline void write(int x){
int top=0,sta[35];
while(x) {sta[top++]=x%10,x/=10;}
while(top) {putchar(sta[--top]+'0');}
}
inline bool comp(int a,int b){
return r[a]>r[b];
}
int main()
{
T=read();
while (T--)
{
n=read(),s1=read(),s2=read();
for (int i=0;i<n;i++) r[i]=read(),id[i]=i;
sort(id,id+n,comp);vector <Node> p(2*n);
for (int i=0;i<n;i++) p[i].s=(i+1)*s1,p[i].pos=0,p[i+n].s=(i+1)*s2,p[i+n].pos=1;
sort(p.begin(),p.end());vector <int> ans[2];
for (int i=0;i<n;i++) ans[p[i].pos].push_back(id[i]);
for (int i=0;i<2;i++)
{
int siz=ans[i].size();
printf("%d ",siz);
for (auto x:ans[i]) printf("%d ",x+1);
puts("");
}
}
return 0;
}
|
$D$
我是采购
