前言
A.
题意 :
给你$x$,$y$ 让你找到一个$(a,b)$
满足$y=x*b^a$
范围$x,y\in(1,100)$
思路:
因为范围很小,显然是可以暴力的
code :
void solve(){
int x,y;cin>>x>>y;
for(int i=1;i<=100;i++){
for(int j=1;j<=100;j++){
if(pow(i,j)*x > y)break;
if(pow(i,j)*x == y){
cout<<j<<" "<<i<<endl;
// cout<<i<<" "<<j<<endl;
return;
}
}
}
cout<<0<<" "<<0<<endl;
}
B.
题意 :
给定两个字符,询问这两个字符的价值
价值如题
思路 :
预处理然后输出即可
code :
typedef pair<char,char> pcc;
typedef vector<int> VI;
map<pcc,int> mp;
void init(){
int idx = 0 ;
for(char i = 'a' ;i<='z';i++){
for(char j = 'a';j<='z';j++){
if(i == j) continue;
++idx;
mp[{i,j}] = idx;
}
}
}
void solve(){
string s;cin>>s;
cout<<mp[{s[0],s[1]}]<<endl;
}
int main(){
init();
int t;cin>>t;while(t--)
solve();
return 0 ;
}
C.
题意 :
给你一个只有$a$的串$s$,同时给一个$t$串含小写字母,$s$中的任意一个$a$可以更改为$t$整串
询问有多少种不同的方案
思路 :
分类+计数
- 如果$t$全是$a$
- 如果只有一个$a$输出$1$
- 否则输出$-1$
- 如果含有$a$ 输出$-1$
- 否则因为每个位置都可以变所以是$2^n$
code:
ll ans ;
ll qmi(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a;
a = a*a;
b >>=1;
}
return res;
}
void solve(){
string a,b;
cin>>a>>b;
//如果b中只有a
int flag = 0 ;
for(auto x : b){
if(x != 'a'){
flag =1 ;
break;
}
}
if(!flag){
if(b.size() == 1){
cout<<"1"<<endl;
return;
}else{
cout<<"-1"<<endl;
}
return;
}
//如果b有a 不管有几个
int cnt = 0 ;
for(auto x : b){
if(x == 'a'){
++cnt;
break;
}
}
if(cnt){
cout<<-1<<endl;
return;
}
//否则就是没有
// ans = qmi(2,a.size());
cout<<(1ll<<(a.size()))<<endl;
}
D.
题意 :
给定一个数组$A[]$,同时有两个空数组$B[],C[]$
对于一次操作 :
- 将$A[]$的最后一位,放到$B[]$的中间
- 将$B[]$的中间,放到$C[]$数组的最后一位
询问这样子是否可以使得$C[]$ 变为一个不下降的序列
思路 :
观察样例我们可以发现,如果将$A[]$从后往前看的话,那么$A[i]$只受到$A[i-1]$的影响
因为$A[i-1]$可以放在后面或者前面,因为我们可以将$A[i]和A[i+1](正序$看成一组,如果存在非降序 关系,我们就交换,最后判断即可
code :
const int N = 2e5+10;
int a[N];
void solve(){
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
if(n&1){
for(int i=1;i<n-1;i+=2){
if(a[i] > a[i+1]) swap(a[i],a[i+1]);
}
}else{
for(int i=0;i<n-1;i+=2)
if(a[i] > a[i+1])swap(a[i],a[i+1]);
}
for(int i=1;i<n;i++){
if(a[i-1] > a[i]){
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;
}
E.
(应该不会被$hack$了 : )
题意 :
给定一个数组$A[]$,你可以进行任意次操作,询问最少操作次数,使得$A[i]=0,A[j]=0$
操作如下 :
选中一个$A[i]$
令$A[i]-2,A[i-1]-1,A[i+1]-1$
思路 :
显然的分类然后处理细节
- $n=1$的情况,特判一下
- 判断操作两个连续的
- 操作间隔一个的
- 直接对最小的两个进行操作的
然后我们分情况进行分析 :
-
判断操作两个连续的
-
如果较大的数可以把较小的数带掉,也就是$a[i]>a[i-1]*2$那么答案就是$a[i]/2$
-
否则我们将$a[i]$和$a[i-1]$看成一个整体,每次操作总价值都$-3$,因此总共需要$(a[i]+a[i-1])/3$的次数
-
操作间隔一个的
-
考虑先对大的进行$-2$的操作,因为影响不到另一个,所以我们求其差值,然后再进行$-2$的操作
-
直接对最小的两个进行操作的
- 排序之后找$a[1]$和$a[2]$即可
Code :
const int N = 2e5+10;
int a[N],n;
int b[N];
void solve(){
cin>>n;
int ans = 0x3f3f3f3f;
for(int i=1;i<=n;i++) cin>>a[i],b[i] = a[i];
//只有一种情况的
if(n == 1){
a[1] ++ ;
cout<<a[1]/2<<endl;
return;
}
//连续的
for(int i=2;i<=n;i++){
int minn= min(a[i],a[i-1]);
int maxn= max(a[i],a[i-1]);
if(maxn > 2*minn){
ans = min(ans , (maxn+1)/2);
continue;
}
int t = (a[i] + a[i-1])/3;
if((a[i] + a[i-1])%3 != 0) t++;
ans = min(ans , t);
}
//间隔的
for(int i=2;i<n;i++){
int t = (abs(a[i-1] - a[i+1])+1)/2;
ans = min(ans,min(a[i-1],a[i+1])+t);
}
//离散的
sort(a+1,a+1+n);
a[1] ++ ;
a[2] ++ ;
ans = min(ans,a[1]/2+a[2]/2);
cout<<ans<<endl;
}
F.
题意 :
(相信很多人都没有看懂题意,我这里详细说一下)
首先给定一个$\*.$的二维矩阵,其中$*$表示桌面上的图标
然后询问有多少图标需要进行移动,并不是问移动的步数
那么移动到哪里去呢 ?
我们知道的是$Win$系统,图标默认是从第一列开始从上到下,然后从左到右,就是要移动到这种$Win$图标的方式,因此也就对应了题目中,如果第一列放满那么就放下一列
对于每次询问,都会将当前位置,删除||增加一个图标
询问需要移动多少图标
思路 :
具体看代码,($F<E$)
Code :
int a[N*N+10];
int n,m,q;
void solve(){
cin>>n>>m>>q;
string s;
int total = 0 ;
for(int i=1;i<=n;i++){
cin>>s;s = " "+s;
for(int j=1;j<=m;j++){
if(s[j] == '*'){
a[(j-1)*n+i] =1 ;
++total;
}
}
}
int et = 0;
for(int i=1;i<=total;i++)
if(a[i]) et++;
while(q --){
int x,y;cin>>x>>y;
int t = (y-1)*n + x;
if(a[t]){
if(t<=total)et--;
a[t] =0 ,total--;
if(a[total+1])et --;
}else{
if(t <= total) et ++;
a[t]= 1,total++;
if(a[total])et++;
}
cout<<total- et<<endl;
}
}
F题确实没看懂,看了博主的翻译之后才懂什么意思,感觉这题可以树状数组啊
的确大佬Orz
好优雅的写法