Codeforces 每日一练 922C+725D+1152D

922C Cave Painting

传送门
镜像
1600的数论水题
题意：1~k中是否存在一对数i,j使得n mod i=n mod j，如果有，输出“No”，否则输出“Yes”
从1向后递推就可以很轻松地看出规律啦，显然n mod 1为0，那么n mod 2只能是1，否则会重复，同理 n mod 3=2,n mod 4=3，可以发现，只有当n mod i=i-1(1<=i<=k)的时候才满足输出“Yes”的条件，那么直接暴力跑就可以过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
using namespace std;
#define ll long long
ll n;
ll k;
int check(){
    if(n!=1&&n<=k)return 0;
    for (ll i = 1; i <=k ; ++i) {
        if(n%i!=(i-1))return 0;
    }
    return 1;
}
signed main()
{
    ios ; cin.tie(0) , cout.tie(0);
    cin>>n>>k;
    if(check())cout<<"Yes";
    else cout<<"No";
    return 0;
}

然而，这道题可以用随机数A掉（来自小姐姐的仙术）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,int> mp1;
map<ll,int> mp2;
ll n,k;
int main()
{
	ios::sync_with_stdio(false);
	auto seed=std::chrono::system_clock::now().time_since_epoch().count();
	std::mt19937 generator(seed);
	cin>>n>>k;
	if(n<=k&&n!=1)
	{
		cout<<"No"<<endl;
		return 0;
	}
	for(int i=1;i<=1000000;i++)
	{
		ll tmp=generator()%k+1;
		if(mp1[tmp])
			continue;
		mp1[tmp]=1;
		if(mp2[n%tmp])
		{
			cout<<"No"<<endl;
			return 0;
		}
		mp2[n%tmp]=1;
	}
	cout<<"Yes"<<endl;
	return 0;
}

725D Contest Balloons

传送门
镜像
1800的优先队列
题意：你的队伍有t个气球，比赛结果按气球数排序，你可以把你的气球分给别的队伍来让他们的气球数大于重量，从而让他们起飞并被取消资格，问最优的名次是多少
先排个序，把比自己多的队伍的t-w+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
#define maxn 300005
struct node{
    ll t,w;
}a[maxn];
priority_queue <ll,vector<ll>,greater<> > q;
ll cmp(node c,node d){
    return c.t>d.t;
}
int main()
{
    scanf("%lld",&n);
    ll tmp,ans=1;
    for (ll i = 0; i <n ; ++i) {
        scanf("%lld %lld",&a[i].t,&a[i].w);
    }
    tmp=a[0].t;
    sort(a+1,a+n,cmp);
    for (;ans<n ; ++ans) {
        if(a[ans].t<=tmp)break;
        q.push(a[ans].w-a[ans].t+1);
    }
    ll pos=ans;
    ll pm=pos;
    while((!q.empty())){
        ll now=q.top();
        tmp-=now;
        if(tmp<0)break;
        q.pop();pm--;
        for (ll i = pos; i<n; ++i) {
            if(a[i].t<=tmp)break;
            ll o=a[i].w-a[i].t+1;
            q.push(o);
            pos++;
            pm++;
        }
        ans=min(ans,pm);
    }
    printf("%lld",ans);
    return 0;
}

（刚开始cmp函数没返回ll，RE了半天~

1152D Neko and Aki’s Prank

传送门
镜像
洛谷
2000的dp
题意：对于长度为2n的合法括号序列（做了那么多次了，合法就不多说了），将所有可能的情况建一个Trie树，取尽量多的边使得所取的边不相交。
受大佬的思想启发，对于两个长度一致的括号序列，如果其中左括号-右括号数量相等，那么他们的子树是等价的，这种情况就可以合并考虑，那么就可以开一个dp[2005][2005]的数组，dp[i][j]表示当前序列长度为i，左括号-右括号数目为j，同时另外开一个二维数组记录当前节点的儿子是否可以和当前节点连边，如果可以连边，那么计算儿子的时候就要加一，并把儿子的状态改为0，否则儿子的状态记为1。
有转移方程：
dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]
c[i][j]=!(c[i-1][j-1]|c[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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
#define maxn 2005
ll dp[maxn][maxn];int c[maxn][maxn];
#define mod 1000000007
int main()
{
    IOS
    cin>>n;
    memset(dp,0, sizeof(dp));
    c[0][0]=1;
    for (int i = 1; i <=2*n ; ++i) {
        for (int j = 0; j <=i ; ++j) {
            ll tmp=0;
            int fl=0;
           if(j>=1){tmp+=dp[i-1][j-1];fl|=c[i-1][j-1];}
           if(j+1<=i-1){tmp+=dp[i-1][j+1];fl|=c[i-1][j+1];}
           if(fl){tmp+=1;c[i][j]=0;}
           else c[i][j]=1;
           dp[i][j]=tmp%mod;
        }
    }
    cout<<dp[2*n][0];
    return 0;
}