前言
中规中矩的一场,难度在$cf\ 1500$左右 (虽然后面几题还没看)
传送门 :
因为是训练赛,忘记按照榜做了,导致歪的有点严重
还有就是$B,C$队友疯狂$WA$,队友很不在状态
A.
题意 :
给定$n,m$的一个矩阵表示敌人的位置
同时给定$a$和$b$
- $a$次可以消灭该行的敌人
- $b$次可以消灭列的敌人
询问是否可以全部消灭
思路 :
因为$n$最多不超过$20$,我们考虑直接暴力枚举选择行的方式
然后去寻找需要删除列的个数即可
如果合法即输出
Code :
const int N = 30;
string s[N];
void solve(){
int n,m,a,b;
cin>>n>>m>>a>>b;
int flag = 0 ;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<(1<<n);i++){
int cnt = 0 ;
for(int j=0;j<n;j++){
if((i>>j)&1) cnt++;
}
if(cnt>a)continue;
int y = 0 ;
for(int j=0;j<m;j++)
for(int k=0;k<n;k++)
if(s[k][j] == '*' && !((i>>k)&1)){
y++;
break;
}
if(y<=b) flag = 1;
}
if(flag){
cout<<"yes"<<endl;
}else cout<<"no"<<endl;
}
int main(){
int t;cin>>t;while(t--)
solve();
return 0 ;
}
B.
题意 :
寻找最小的$n$,使得$n!=p$
思路 :
首先口胡一下,单调性
根据算数基本定理可以将一个数进行质因数分解,对于$mid$越大,那么能被分解出来的次幂就越大,因此我们只需要不断二分出来$mid$
然后令$mid/prime[p]$,即将$p$进行质因数分解,比较$mid$中含有$p$质因数的次幂和$p$质因数的次幂即可
code :
const int N = 1e5+10;
int prime[N],mi[N];
int idx;
ll q;
void get_pri(int n){
idx = 0 ;
for(int i=2;i<=n/i;i++){
if(n%i == 0){
prime[++idx] = i;
while(n%i == 0 ){
mi[idx] ++;
n/=i;
}
}
}
if(n>1){
prime[++idx] = n;
mi[idx]++;
}
}
bool check(int x){
for(int i=1;i<=idx;i++){
int sum = 0 , t = x;
while(t){
sum+=t/prime[i];
t/=prime[i];
}
if(sum < mi[i])return false;
}
return true;
}
void solve(){
cin>>q;
ll l = 1 , r = q;
memset(prime,0,sizeof prime);
memset(mi,0,sizeof mi);
get_pri(q);
while(l<=r){
ll mid = (l+r)>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
cout<<l<<endl;
}
int main(){
int t;cin>>t;while(t--)
solve();
return 0 ;
}
C.
题意 :
给定一个$n$顶点的完全图,你可以删除$m$条边,询问最多可以出现几个连通块
思路 :
因为是完全图,所以对于一个顶点的独立,一定是$n-1…n-2…n-3…1$这样子递减的消费
因此我们考虑二分一个$x$
使得$\sum(n-1....1) -\sum(x…1) <m$即可
但是这题很鬼,用$ll$过不了,用$unsigned$会 $TLE$
虽然有考虑优化求和公式,但是还是开了一个$128$水过去了
code:
__int128 n,m,sum;
bool check(__int128 x){//第n个节点不能删除
__int128 sum1 = (1+x)*x/2;
//那么就是已经删除了这么多
if(sum - sum1 > m) return false;
else return true;
}
void solve(){
n = read();
m = read();
sum = (1+(n-1))*(n-1)/2;
__int128 l = 0 , r = n;
while(l<=r){
__int128 mid = (l+r)>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
write(n-l);
cout<<endl;
// cout<<(n-l)<<endl;
}
signed main(){
int t;cin>>t;while(t--)
solve();
return 0 ;
}
E.
题意 :
给定一个范围在$2^{32}$的一个数$c$
求$c=a+b$的选法,$a,b\in 2^{32}$
思路 :
显然,答案是唯一的
code:
cout<<"4294967296"<<endl;
I.寻找子串
题意 ：
给定一个字符串,寻找字典序多大的连续子串
思路 :
因为长度范围很小所以考虑直接暴力枚举子串
思路 :
void solve()
{
string str;
cin>>str;
string ans;
int len=str.length();
bool flag=false;
for(int i=0;i<len;i++)
for(int j=1;j<=len;j++)
{
if(!flag)
{
ans=str.substr(i,j);
flag=true;
}
else ans=max(ans,str.substr(i,j));
}
// sort(vt.begin(),vt.end());
cout<<ans;
}
J.最大的差
题意 :
给定一个$a[]$,从中寻找两个数使得差最大
思路 :
....
总结 :
因为$G$卡了很久,导致肚子很饿而且还没有调出来,所以没有开$H$题,显然思维 和 手速都没跟上
同时$I$题,寻找子串的题还读假了,而且我处理字符串问题还很吃力,所以导致这一场并不是很出色。显然还有许多地方需要加强
