Codeforces 每日一练 629C+958E1+1237C1

629C Famil Door and Brackets

题意：给定一个只有 ( 和 ) 的长度为m的字符串，询问在左右两边有多少种加括号的方案可以使这个序列成为一个合法的括号序列。
传送门
dp没思路怎么办？看数据范围。虽然n和m都是1e5的范围，但是n-m只有2000，那么很有可能是开一个二维dp去解决问题。根据题目中的描述，如果我们记录前 i 个字符中 ( 比 ) 多的数目sum，那么显然有sum>=0，那么我们不妨开一个二维数组dp[i][j]记录前 i 个字符sum为 j 的方案数，i<=n-m，那么我们只需要枚举可能的 j 的取值去计算答案就好，在考虑 q 的方案数时，我们同样可以利用之前的dp数组，只需要把sum看作 ) 比 ( 多的数目即可。

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>
using namespace std;
#define ll long long
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define maxn 2005
#define int long long
int dp[maxn][maxn];
signed main(){
    IOS
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    int l=0,r=0,ma=-3e10;
    for (int i = 0; i <s.size() ; ++i) {
        if(s[i]=='(')l++;
        else r++;
        ma=max(ma,r-l);
    }
    if(abs(l-r)>n-m||n%2!=0){
        cout<<0;
    }else{
        dp[0][0]=1;
        for (int i = 1; i <=2000 ; ++i) {
            dp[i][0]=dp[i-1][1];
            for (int j = 1; j <=i ; ++j) {
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%mod;
            }
        }
        int sum=0;
        for (int i = 0; i <=n-m ; ++i) {
            for (int j = 0; j <=n-m ; ++j) {
                if(j>=ma&&j+l-r<=n-m){
                    sum+=dp[i][j]*dp[n-m-i][j+l-r]%mod;
                    sum%=mod;
                }
            }
        }
        cout<<sum;
    }
    return 0;
}

958E1 Guard Duty (easy)

传送门
题意：给定r个飞船和b个基地的坐标，判断能否将飞船和基地一一配对，并且使连线互不相交。
想了半天，发现题目里保证两点不重叠并且任意三点不共线……那这道题就很水了 ，只需要判断r和b是否相同即可。对于任意一对相交的AB,CD，我们可以重连为AC，BD令他们不相交，所以唯一No的情况就是r!=b.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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);
signed main(){
    IOS
    int m,n;
    cin>>n>>m;
    if(m!=n){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
    return 0;
}

1237C1 Balanced Removals (Easier)

传送门
题意：每次选择两个点删去，并且两个点形成的长方体内不含其他点，输出一种方案。
贪心的做法就是每次选择当前剩余节点里距离最近的就行，n^2跑一遍即可。

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
#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);
#define maxn 2005
#define int long long
struct node{
    int x,y,z;
    int id;
};
node a[maxn];
bool cmp(node c,node b){
    if(c.x!=b.x)return c.x<b.x;
    if(c.y!=b.y)return c.y<b.y;
    return c.z<b.z;
}
int vis[maxn]={0};
int dis( node c, node d){
    return (c.x-d.x)*(c.x-d.x)+(c.y-d.y)*(c.y-d.y)+(c.z-d.z)*(c.z-d.z);
}
signed main(){
    IOS
    int n;
    cin>>n;
    for (int i = 1; i <=n ; ++i) {
        cin>>a[i].x>>a[i].y>>a[i].z;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    int cnt=0,tmp=1;
    while(cnt!=n){
        for (int k = 1; k <=n ; ++k) {
            if(vis[k]==0){
                tmp=k;
                break;
            }
        }vis[tmp]=1;
        int mi=0x3f3f3f3f3f3f3f3f;
        int pos=1;
        for (int i = 1; i <=n ; ++i) {
            if(dis(a[i],a[tmp])<mi&&vis[i]==0){
                mi=dis(a[i],a[tmp]);
                pos=i;
            }
        }
        vis[pos]=1;

        cout<<a[tmp].id<<" "<<a[pos].id<<endl;
        cnt+=2;
    }
    return 0;
}