牛客小白月赛23

发表于 |
字数统计: 1.4k | 阅读时长 ≈ 7

所有的伟大，都是从最初的平凡开始的。

题目链接点击就进去了

A

题意：一个图大小最大为（n行m列）20行100000列，带有*和.的图，每次可以消除a行b列，问采用最佳的消除方式能否把带星星的消除掉。

题解：dfs暴力，因为只有20行复杂度只是2^20，然后在乘以m，总的复杂度为2 ^ 20 * m,这么暴力竟然过了

思路：主要思路是dfs，深搜，如果深搜到最后一行的话直接return了，当回溯到最后一行且，消除的行数达到最大的时候的话,并且这种方式剩下待消灭的列可以被消灭则将标识位flag标记为true，这个是回溯的源头，也就是有解的标志，如果没达到最后一行的话，就一直，回溯下去，往下一行，继续深搜，如果好了的话就剪枝，如果没好的话就接着回溯，这次already+1，然后给当前行标记上。

代码：

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
#include<iostream>
using namespace std;
const int maxn=1e5+1;
int vis[maxn];
char g[21][maxn];
int n,m,a,b;
bool flag=false;
bool check()
{
	int res=0;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(!vis[j] && g[j][i]=='*'){
				res++;
				break;
			}
		}
	}
	if(res>b) return false;
	else return true;
}
void dfs(int now,int already){
	if(now==n){
		if(already==a && check()){
			flag=true;
		}
		return;
	}
	vis[now]=0;
	dfs(now+1,already);
	if(flag) return ;
	if(already<a){
		vis[now]=1;
		dfs(now+1,already+1);
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		flag=false;
		cin>>n>>m>>a>>b;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				cin>>g[i][j];
			}
		}
		dfs(0,0);
		if(flag) cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	return 0;
}

B

题意：输入p，找出最小的n，使得 n！% p == 0成立。
题解：怎么搞呢？？？涉及到知识盲区了……，emmmm，python？
对忘了我会python了。。。。。。
试一下吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
t = int(input())
sum = 1
k = 0
while t:
    t-=1
    sum = 1
    p = int(input())
    for i in range(1,p+1):
        sum *= i
        if sum%p==0 :
            k=i
            break
    print(k)

这个题有点强把python给卡了，好像的确会卡掉。。。
TLE
那下面进入正解吧。
思路：类似与素数筛吧，先对p元素进行质因子分解，然后采取二分的方法，l=0，r=p，即可，然后mid，判断它的每个质因子个数，是否，比p的质因数个数多，如果多的话，说明mid偏大了，则右区间左移动，如果少的话，则左区间右移，二分用那个二进制移位比较好，可以防止l+r超出整型的范围。
代码：

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
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1e5+10;
int p,num[maxn],prime[maxn],k;
bool judge(int x)
{
	for(int i=1;i<=k;i++)
	{
		int n=x,num_prime=0;
		while(n){
			num_prime+=n/prime[i];
			n/=prime[i];
		}
		if(num_prime<num[i]) return false;
	}
	return true;
}
void solve()
{
	k=0;
	//分解P的质因数
	for(int i=2;i*i<=p;i++)
	{
		if(p%i==0)
		{
			prime[++k]=i;
			while(p%i==0){
				num[k]++;
				p/=i;
			}
		}
	}
	//这个是一个细节，如果p是质数的话，就直接把P仍进去就好了
	if(p>1) {
		prime[++k]=p;
		num[k]++;
	}
	int l=1,r=1e9,ans;
	//二分，judge函数，是判断mid的质因数个数，和p的质因数个数的比较
	//这样就可以有效的二分出来
	while(l<=r){
		int mid=(l+r)>>1;
		if(judge(mid)){
			r=mid-1;
			ans=mid;
		}else
			l=mid+1;
	}
	memset(num,0,sizeof(num));
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		cin>>p;
		solve();
	}
	return 0;
}

E

签到题吧……

题目链接自己理解E
永远都是2^32次方吧

python最短代码

1
print(4294967296)

I

题意：寻找最大连续子串，
比如acbcc 的最大自串是cc ， abc的最大子串是c，helloworld的最大子串是world，然后按题意暴力就行

题解：暴力，找出最大字母，记录下位置来，然后判断每个最大子串的大小，大的后缀替换掉前面的就行了

代码：

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
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s;
int pos,cnt,r,l;
bool pd(int l,int r)
{
	string s1,s2;
	s1=s.substr(l,s.size()-l);
	s2=s.substr(r,s.size()-r);
	if(s1>s2) return true;
	else	return false;
}
int main()
{
	SIS;
	//加速cin/cout
	cin>>s;
	char c=s[0];
	for(int i=1;i<s.size();i++)
	{
		if(s[i]>c){
			pos=i;
			c=s[i];
		}
	}
	int tl,tr;
	l=pos;
	for(int i=pos+1;i<s.size();i++)
	{
		if(s[i]==c){
			r=i;
		if(!pd(l,r)) l=r;
		}
	}
	for(int i=l;i<s.size();i++)
		cout<<s[i];
	return 0;
}

J

题意：给一串数字，找出其中差值最大的数来，并输出最大差值
我是用set维护，取第一个和最后一个就行了，其实直接min，max统计也行，而且不占内存
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int main()
{
	SIS;
	//加速cin/cout
	int n;
	cin>>n;
	set<int> st;
	for(int i=1;i<=n;i++){
		int t;cin>>t;st.insert(t);
	}
	set<int> ::iterator it=st.begin(),ee=st.end();
	ee--;
	int k1=*it,k2=*ee;
	cout<<k2-k1<<endl;
	return 0;
}
-------------本文结束感谢您这么好看还看我的文章-------------