AtCoder Beginner Contest 185.

Task Name Time Limit Memory Limit
A ABC Preparation 2 sec 1024 MB Submit
B Smartphone Addiction 2 sec 1024 MB Submit
C Duodecim Ferra 2 sec 1024 MB Submit
D Stamp 2 sec 1024 MB Submit
E Sequence Matching 2 sec 1024 MB Submit
F Range Xor Query 3 sec 1024 MB Submit

A

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
cout<<min(a,min(b,min(c,d)));

}

B

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
ll n,m,t;
cin>>n>>m>>t;
ll c=n;
ll pre=0;
for(int i=1;i<=m;i++)
{
    ll x,y;
    cin>>x>>y;
    n-=(x-pre);
    pre=y;
    if(n<=0)
    {
cout<<"No";
return 0;
    }
    else
    {
        n=min((n+y-x),c);
        //注意这一句，没有这一句wa了2
    }
}
if(n-t+pre>0)
{
cout<<"Yes";
}
else
{
    cout<<"No";
}

}

C

\(C_{X-1}^{11}\)

C题其实就是从x-1选11

组合数板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll comb[400][400];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll x;
cin>>x;
 for(int i = 0; i <=x ; i ++){
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j ++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            }
    }
cout<<comb[x-1][11];
}

D

由于可以覆盖直接找到最小的，然后取整相加，一开始以为不可以重叠当gcd做了

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
int a[N];
int b[N];
int cnt;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a[i];
    }
    a[k+1]=n+1;
    sort(a+1,a+1+k+1);
    int pre=0;
    int minn=1e9;
    for(int i=1;i<=k+1;i++)
    {
        if(a[i]-pre-1==0)
        {
            pre=a[i];
            continue;
        }
        minn=min(a[i]-pre-1,minn);
        b[++cnt]=a[i]-pre-1;
        pre=a[i];
    }
int ans=0;
for(int i=1;i<=cnt;i++)
{
    ans+=(b[i]+minn-1)/minn;
}
cout<<ans;


}

E

首先遍历 \(a\) 与 \(b\)，若有相等转移方程即为 \(dp_{i,j}=dp_{i-1, j-1}\)，如果不等转移方程即为 \(dp_{i,j} = \min(dp_{i,j-1},\min(dp_{i-1,j-1},dp_{i-1,j})) + 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
// LUOGU_RID: 156459169
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
//删除，插入，修改
//毫无思路，于是dp
//数据范围是支持n^2的
int dp[2002][2002];
int a[2002];
int b[2002];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
for(int i=1;i<=m;i++)
{
    cin>>b[i];
}
for(int i=1;i<=n;i++)
{
    dp[i][0]=i;
}
for(int i=1;i<=m;i++)
{
    dp[0][i]=i;
}
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(a[i]==b[j])
        {
            dp[i][j]=dp[i-1][j-1];
        }
        else
    {
        dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
    }
    }
}
cout<<dp[n][m];


}

F

单点修改区间查询（异或前缀和）

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
// LUOGU_RID: 156461193
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
using ll=long long;
const int N=2e6+100;
ll a[N],n;
//删除，插入，修改
//毫无思路，于是dp
//数据范围是支持n^2的
void add(ll x,ll v)
{
    while(x<=n)
    {
        a[x]^=v;
        x+=lowbit(x);
    }
}
int query(int x) 
{
	int res=0;
	while(x)
	res^=a[x],x-=lowbit(x);
	return res;
}
int main()
{
ll m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) 
    {
		ll x;
		cin>>x;
		add(i,x);
	}
	while(m--) 
    {
		ll opt,l,r;
		cin>>opt>>l>>r;
		if(opt==1)
		add(l,r); 
        else
		cout<<(query(r)^query(l-1))<<endl;
	}

}