AcWing第 68 场周赛题解

AcWing 4612. 去掉0

求在被1包含的0的个数，思路是正逆分别计算0的位置，取交集.

void solve()
{
    string s;
    cin>>s;
    int cnt=0;
    bool f=false;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1')f=true;
        else if(f)s[i]='2';
    }
    f=false;
    for(int i=s.size()-1;i>=0;i--)
    {
        if(s[i]=='1')f=true;
        else if(f&&s[i]=='2')s[i]++;
    }
    for(auto x:s)if(x=='3')cnt++;
    cout<<cnt<<endl;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

AcWing 4613. 方格跳跃

前缀和后缀分别是连续的<和>才能出界

#include 
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int i=0;
    int res=0;
    while(i<n&&s[i]=='<')res++,i++;
    i=n-1;
    while(i>=0&&s[i]=='>')res++,i--;
    cout<<res<<endl;
} 
signed main()
{
    io;
    int _;_=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

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

AcWing 4614. 匹配价值

暴力枚举，详细看注释

#include 
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n,m,q;
const int N=1<<13,M=5e5+10;
int w[20],cnt[N];//位权值，string的个数
unordered_map<string,int>mp;//二进制string->十进制int
int f[N][110];//f[i][j] i对应的和不超过j的个数
string t;
int k;
void solve()
{
	cin>>n>>m>>q;
	rep(i,0,n-1)cin>>w[i];
	rep(i,0,(1<<n)-1)//hash 
	{
		int t=0;
		string s;
		dwn(j,n-1,0)
		{
			int x=i>>j&1;
			t=t*2+x;
			s+=x+'0';
		}
		reverse(s.begin(),s.end());
		mp[s]=t;
	}
	rep(i,1,m)
	{
		string s;
		cin>>s;
		cnt[mp[s]]++;//count
	}
	rep(i,0,(1<<n)-1)//暴力枚举
	{
		if(!cnt[i])continue;
		rep(j,0,(1<<12)-1)
		{
			int sum=0;
			rep(k,0,n-1)
				sum+=!((i^j)>>k&1)*w[k];
			if(sum<=100)f[j][sum]+=cnt[i];//超过题目要求的权值和就没必要存了
		}
	}
	rep(i,0,(1<<12)-1)//前缀和
		rep(j,0,100)
			f[i][j]+=f[i][j-1];
		
	while(q--)
	{
		cin>>t>>k;
		cout<<f[mp[t]][k]<<endl;
	}
} 
signed main()
{
    io;
    int _;_=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83