补几道
A. 清楚姐姐学信息论
题面
非常有意思的一道题，乍一看肯定是低进制效率高，但被WA教训之后开始冷静思考
x 进制与 y 进制比较效率， x ⋅ y 张号码牌在 x 进制下是 y 位， y 进制下是 x 位
分别能表示的数的个数为 xy 和 yx
现在就是比较这两个数的大小
因为 x ， y 都大于 1 ，可以取对数，大小关系不变
即比较 yln x 与 xln y 的大小关系
即比较
同构，构造函数
所以 maxf(x) = max(f(2),f(3)) ，即 f(3) 最大，而 f(2) > f(4) ，所以可以得出全部的大小顺序
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
ll x,y;
cin>>x>>y;
if(x==3||y==3)
cout<<3<<'\n';
else
cout<<min(x,y)<<'\n';
return 0;
}
B. 清楚姐姐学构造
题面
由题意可知：
ci ≡ ai + bi mod m cN − 1 − i ≡ aN − 1 − i + bN − 1 − i ≡ ai − bi mod m
所以
如果 m = 2 ，那么可能无解，需要判断一下
如果 m > 2 ，那么 (2,m) = 1 ， 2 在模 m 下有逆元，找出逆元乘一下就行
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
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll c[N];
void Exgcd(ll a,ll b,ll &x,ll &y){
if(!b) x=1,y=0;
else Exgcd(b,a%b,y,x),y-=a/b*x;
}
int inverse(ll a,ll p){
ll x, y;
Exgcd (a,p,x,y);
x=(x%p+p)%p;
return x;
}
int main() {
ios::sync_with_stdio(false);
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>c[i];
if(m==2)
{
bool flag=false;
for(int i=1,j=n;i<=j;i++,j--)
{
if((c[i]+c[j])%2!=0)
{
flag=true;
break;
}
}
if(flag)
cout<<"No"<<'\n';
else
{
cout<<"Yes"<<'\n';
for(int i=1;i<=n;i++)
cout<<c[i]<<' ';
cout<<'\n';
for(int i=1;i<=n;i++)
cout<<0<<' ';
cout<<'\n';
}
}
else
{
cout<<"Yes"<<'\n';
ll s=inverse(2,m);
for(int i=1;i<=n;i++)
cout<<(c[i]+c[n+1-i])%m*s%m<<' ';
cout<<'\n';
for(int i=1;i<=n;i++)
cout<<(c[i]-c[n+1-i]+m)%m*s%m<<' ';
cout<<'\n';
}
return 0;
}
E. 清楚姐姐打怪升级
题面
模拟一下就行
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
using namespace std;
typedef long long ll;
const int N=1e5+5;
int h[N],v[N];
ll ceil(ll x,ll y)
{
if(x%y==0)
return x/y;
return x/y+1;
}
int main() {
ios::sync_with_stdio(false);
int n,t,a;
cin>>n>>t>>a;
bool flag=false;
for(int i=1;i<=n;i++)
{
cin>>h[i]>>v[i];
if(v[i]*t>=a&&h[i]>a)
flag=true;
}
if(flag)
cout<<-1<<'\n';
else
{
ll cnt=0;
for(int i=1;i<=n;i++)
{
if(h[i]>=a&&v[i]*t<a)
cnt+=ceil(h[i]-a,a-v[i]*t)+1;
else
cnt++;
}
cout<<1+(cnt-1)*t<<'\n';
}
return 0;
}
L. 清楚姐姐的三角形I
题面
直接能算出来，判断一下就行
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
using namespace std;
typedef long long ll;
ll v[3];
ll l[3];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
ll sum=0;
for(int i=0;i<3;i++)
{
cin>>v[i];
sum+=v[i];
}
if(sum%2!=0)
cout<<"No"<<'\n';
else
{
sum/=2;
for(int i=0;i<3;i++)
l[i]=sum-v[i];
sort(l,l+3);
if(l[0]+l[1]>l[2])
{
cout<<"Yes"<<'\n';
for(int i=0;i<3;i++)
cout<<sum-v[i]<<' ';
cout<<'\n';
}
else
cout<<"No"<<'\n';
}
}
return 0;
}
M. 清楚姐姐的三角形II
题面
显然有循环，构造 1,2,4,1,2,4,…这样就行
1 |
|