Codeforces Round #501 (Div. 3) 训练总结及题解

A题因为交了错了文件和试样例慢了2mins用了5mins，B题读题较慢用了13mins，C题读题也偏慢用了7mins，D题少考虑一种情况wa了3发用时22mins，E题读错了判断条件，写完用了40mins。F题场后看题解学会。
总结：

1. 每次文件要在场前调整好。
2. 过了A题仍要快速读题。
3. D题的多种情况，wa了一发之后要多考虑。
4. E题太浮躁了，不愿意重读题，靠样例猜题意。

题解：
A.
题意：给你n个区间，m代表总区间1-m，现判断给的n区间与总区间未交集的范围的总数。
思路：暴力即可，数据范围大可以用线段树，或者预处理。
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e3+5;
bool vis[maxn];

int main(){
    IO;
    int n,m;cin>>n>>m;
    forn(i,n){
        int l,r;cin>>l>>r;
        for(int i = l;i<=r;i++) vis[i] = 1;
    }
    vector<int>ans;
    for1(i,m) if(!vis[i]) ans.push_back(i);
    cout << ans.size()<<'
';
    for(auto x:ans) cout << x<< ' ';







    return 0;
}

B
题意：给字符串s和t，长度50，问是否可以移动最多1e4次，每次仅可移动相邻位置，使得t==s。
思路：暴力移动(On^2）
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int num[26],num2[26];
int main(){
    IO;
    int n;cin>>n;
    string s,t;cin>>s>>t;
    forn(i,n){
        num[s[i]-'a']++;
        num2[t[i]-'a']++;
    }
    vector<int>ans;
    forn(i,26)if(num[i]!=num2[i])return cout<<-1<<'
',0;
    forn(i,n){
        if(s[i]!=t[i]){
            int pos = i;
            for(int j = i;j<n;j++){
                if(s[j]==t[i]){
                    pos = j;break;
                }
            }
            for(int j = pos-1;j>=i;j--){
                swap(s[j+1],s[j]);
                ans.push_back(j+1);
            }
        }
    }

    cout << ans.size()<<'
';

    for(auto x:ans) cout <<x<<' ';





    return 0;
}

C.
题意：给n个物品1e5，一个限制k1e9。每个物品有一个初始值和变动值。问最少改动多少初始值使得所有物品sum<=k。
思路：排序
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
    IO;
    int n,m;cin>>n>>m;
    vector<int>a(n);ll sum = 0;
    forn(i,n){
        int x,y;cin>>x>>y;
        a[i] = x-y;
        sum+=x;
    }
    sort(a.begin(),a.end());
    if(sum<=m) return cout << 0<<'
',0;
    forn(i,n){
        sum-=a.back();a.pop_back();
        if(sum<=m) return cout << i+1<<'
',0;
    }
    cout << -1 <<'
';





    return 0;
}

D
题意：一个区间1,n1e9。初始在1点，问是否可以移动m2e5次使得移动总距离达到k1e18。不可以输出-1，可以构造出来每次移动至何点。
思路：数学，有坑点：1.longlong 2.移动可能不达k次
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
    IO;
    ll n,m,s;cin>>n>>m>>s;
    //n= 1e9,m= 2e5,s=1e18;
    //cerr<<(n-1)*m<<'
';
    if(1ll*(n-1)*m<s) return cout<<"NO"<<'
',0;
    if(m>s) return cout<<"NO"<<'
',0;
    cout <<"YES"<<'
';
    ll v = s/m,x = s%m;
    vector<ll>ans(m);
    ll pos = 1;
    forn(i,m){
        if(i&1){
            pos-=v;
            if(x>0)pos--;
        }
        else{
            pos+=v;
            if(x>0)pos++;
        }
        x--;
        ans[i] = pos;
    }
    for(auto x:ans) cout <<x<<' ';


    return 0;
}

E
题意：让你在图中找到x个由’'组成的十字架，x<nm，问十字架能否覆盖所有*，可以的话输出每个十字架的中心位置和他的长度。
思路：出题人低估了cf的评测姬ON^3也可过。
On^2是用dp先预处理四个数组及每个点向上下左右最远的‘.’距离。然后取四数组min，再dp或者其他方法把覆盖点去掉，最后输出。
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

char a[1005][1005];
int d[1005][1005],u[1005][1005],l[1005][1005],r[1005][1005];
int pos[1005][1005],pos2[1005][1005];
vector<pair<pair<int,int>,int> >ans;

int main(){
    //IO;
    int n,m;cin>>n>>m;
    for1(i,n) for1(j,m) cin>>a[i][j];
    for1(i,n){
        for1(j,m){
            if(a[i-1][j]=='*') u[i][j] = u[i-1][j]+1;
            if(a[i][j-1]=='*') l[i][j] = l[i][j-1]+1;
        }
    }
    for(int i = n;i>=1;i--){
        for(int j = m;j>=1;j--){
            if(a[i+1][j]=='*') d[i][j] = d[i+1][j]+1;
            if(a[i][j+1]=='*') r[i][j] = r[i][j+1]+1;
        }
    }
    for1(i,n)for1(j,m)if(a[i][j]=='*'){
        int len = min({u[i][j],r[i][j],l[i][j],d[i][j]});
        if(len){
            ans.push_back({{i,j},len});
            pos[i][j-len]--;
            pos[i][j+len+1]++;
            pos2[i-len][j]--;
            pos2[i+len+1][j]++;
        }
    }
    for1(i,n){
        int cnt = 0;
        for1(j,m){
            cnt+=pos[i][j];
            if(cnt!=0) a[i][j] = '.'; 
        }
    }
    for1(j,m){
        int cnt = 0;
        for1(i,n){
            cnt+=pos2[i][j];
            if(cnt!=0) a[i][j] = '.';
        }
    }
    /* err<<'
';
    for1(i,n){
        for1(j,m)cerr<<a[i][j];
        cerr<<'
';
    }*/
    for1(i,n)for1(j,m)if(a[i][j]=='*')return cout <<-1<<'
',0;
    cout << ans.size()<<'
';
    for(auto x:ans){
        cout <<x.first.first<<' '<<x.first.second<<' '<<x.second<<'
';
    }

    return 0;
}

F
题意：给你一个括号序列S，再给你一个N，求长度为2N，且含有子串S，满足括号匹配的序列总数。
思路：第一次做字符串dp，跟ac自动机的题有点像。思路随意构造，看能否构造包含s的长度为2*n的母串。
dpijk，i表示构造到第几位，j表示’(‘的个数 -’)’的个数，k表示构造当前情况和子串相同到了第k位。
状态转移考虑两种情况
sk==’(‘和sk==’)‘及所枚举的这种情况到达s串的第k位等于’(‘或等于’)’
那么构造时候分两种往末尾添加相同的字符和不相同的字符，不相同的时候类似kmp和ac自动机找到失配的位置。
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
ll dp[205][105][205],nex[205],fail1[205],fail2[205],fail[205];
const ll mod = 1e9+7;
void getnex(string s){
    ll len = s.size(),i = 0,j = -1;
    nex[0] = -1;
    while(i<len){
        if(s[i]==s[j]||j==-1) nex[++i] = ++j;
        else j = nex[j];
    }
    for1(i,len-1)if(nex[i]){
        ll x = nex[i];
        while(s[x]!='('){
            x = nex[x];
            if(!x)break;
        }
        fail1[i] = x; 
        x = nex[i];
        while(s[x]!=')'){
            x = nex[x];
            if(!x)break;
        }
        fail2[i] = x;
    }
}
void build_fail(string s) {
    ll slen = s.size();
    ll j=0;
    for(ll i=1;i<slen-1;i++) {
        while(j&&s[j]!=s[i]) j=fail[j];
        if(s[i]==s[j]) j++;
        fail[i+1]=j;
    }
    //forn(i,slen+1) cerr<<fail[i]<<' ';
   // cerr<<'
';

    for(ll i=slen-1;i;i--) {
        ll j=i;
        while(j&&s[i]==s[j]) j=fail[j];
        if(s[i]!=s[j]) j++;
        fail[i]=j;
    }//forn(i,slen+1) cerr<<fail[i]<<' ';
   // cerr<<'
';
}

int main(){
    IO;
    ll n;string s;cin>>n>>s;
    ll len = s.size();
    //getnex(s);
    build_fail(s);
    dp[0][0][0] = 1;
    forn(i,n<<1){
        forn(j,n+1){
            forn(k,len){
                if(s[k]=='('){
                    (dp[i+1][j+1][k+1] += dp[i][j][k])%=mod;
                    if(j) (dp[i+1][j-1][fail[k]] += dp[i][j][k])%=mod;
                }else{
                    (dp[i+1][j+1][fail[k]] += dp[i][j][k])%=mod;
                    if(j) (dp[i+1][j-1][k+1] += dp[i][j][k])%=mod;
                }
            }
            (dp[i+1][j+1][len] += dp[i][j][len])%=mod;
            if(j)  (dp[i+1][j-1][len] += dp[i][j][len])%=mod;
        }
    }
    /* forn(i,n<<1+1){
        forn(j,n+1){
            forn(k,len+1){
                cerr<<dp[i][j][k]<<' ';
            }
            cerr<<'
';
        }
        cerr<<"!@#"<<'
';
    }*/
    cout <<dp[n<<1][0][len]<<'
';
    /*5
()))() */
    return 0;
}