Educational Codeforces Round 115 (Rated for Div. 2)题解A-F

Educational Codeforces Round 115 (Rated for Div. 2) A. Computer Game

分析：

输出YES当且仅当，每一列都至少存在一个0.

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define close(); 	ios::sync_with_stdio(false);
#define endl "n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int dp[N];
char mp[2][N];
void solve()
{
    int n; scanf("%d",&n);
    scanf("%s %s",&mp[0][1],&mp[1][1]);
    dp[1] = 1;
    qf(i, 2, n) 
    {
        if((mp[0][i] == '0' || mp[1][i] == '0') && dp[i-1] == 1) dp[i] = 1;
        else dp[i] = 0;
    }
    if(dp[n]) printf("YESn");
    else printf("NOn");
}

int main()
{
    int T; scanf("%d",&T);
    while(T--) solve();
    // system("pause");
}

B. Groups

分析:

暴力枚举选取的两天, 然后检查是否可行即可.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define close(); 	ios::sync_with_stdio(false);
#define endl "n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int dp[N];
char a[N][6];
void solve()
{
    int n; scanf("%d",&n);
    qf(i, 1, n) qf(j, 1, 5) sf("%d",&a[i][j]);
    bool f = 0;
    qf(i, 1, 5)
    {
        qf(j, i+1, 5) 
        {
            int x, y, z, d; x = y = z = d = 0;
            qf(k, 1, n)
            {
                if(a[k][i] == 1 && a[k][j] == 0) x++;
                else if(a[k][i] == 0 && a[k][j] == 1) y++;
                else if(a[k][i] == 1 && a[k][j] == 1) z++;
                else d++;
            }
            if(d != 0) continue;
            // pf("%d, %d: %d %d %dn",i,j,x,y,z);
            if( x <= n/2 && y <= n/2 ) f = 1;
        }
    }
    if(f) pf("YESn");
    else pf("NOn");
}

int main()
{
    int T; scanf("%d",&T);
    while(T--) solve();
    // system("pause");
}

C. Delete Two Elements

分析:

不妨设数组和为sum.

不难将问题转化为求数组a中有多少有序对 < i , j > 使得 a i + a j = = s u m ∗ 2 / n a_i+a_j==sum*2/n ai+aj==sum∗2/n

上map即可.

代码:

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define close(); 	ios::sync_with_stdio(false);
#define endl "n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
map mp;
void solve()
{
    mp.clear();
    int n; scanf("%d",&n);
    LL sum = 0;
    qf(i, 1, n) 
    {
        int ai;
        sf("%d",&ai);
        sum += ai;
        if(mp.find(ai) == mp.end()) mp[ai] = 1;
        else mp[ai]++;
    }
    int k = sum * 2 / n;
    if( sum * 2 % n != 0 ) { pf("0n"); return; }
    LL ans = 0;
    for( auto p = mp.begin(); p != mp.end(); p++ )
    {
        if(mp.find(k-p->first) == mp.end()) continue;
        if(k - p->first == p->first)
        {
            ans += (p->second) * (LL)(p->second - 1);
        }
        else
        {
            ans += p->second * (LL)(mp.find(k-p->first)->second);
        }
    }
    pf("%lldn",ans/2);
}

int main()
{
    int T; scanf("%d",&T);
    while(T--) solve();
    // system("pause");
}

D. Training Session

分析:

求至少符合题中所给两条件之一的情况的个数很难.

不妨求都不符合题中所给两条件的情况的个数, 再拿总的个数去减, 即可出答案.

观察
a a x y b b begin{matrix} a & a & x \ y & b & b end{matrix} ayabxb
不难发现, 不符合题中所给两条件的情况必为上式所给形式.

map瞎搞一下即可.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define close(); 	ios::sync_with_stdio(false);
#define endl "n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
vector T[N], D[N];
void solve()
{
    LL n; sf("%lld",&n);
    qf(i, 1, n) { T[i].clear(); D[i].clear(); }
    LL sum = n*(n-1)*(n-2)/6;
    qf(i, 1, n)
    {
        int t, d; sf("%d %d",&t,&d);
        T[t].push_back(d);
        D[d].push_back(t);
    }
    LL p2 = 0;
    qf(i, 1, n)
    {
        for(int e: T[i])
        {
            p2 += (LL)(D[e].size() - 1) * (LL)(T[i].size() - 1);
        }
    }
    pf("%lldn",sum-p2);
}

int main()
{
    int T; scanf("%d",&T);
    while(T--) solve();
    // system("pause");
}

E. Staircases

分析:

不难发现每次翻转一个方块, 受影响的方块有 [ 1 , 3 n − 2 ] [1, 3n-2] [1,3n−2]个.

记 d p [ i ] [ j ] [ 0 ] dp[i][j][0] dp[i][j][0] 表示以方块ij结尾的1型阶梯的个数, d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1] 表示以方块ij结尾的2型阶梯的个数.

先dp一遍, 把所有方块的状态都算出来, 再对于每个询问暴力更新即可.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define close(); 	ios::sync_with_stdio(false);
#define endl "n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 1024;
LL n, m, q; 
LL sum = 0;
LL f[N][N][2];

void show()
{
    qf(i, 1, n)
    {
        qf(j, 1, m)
        pf("%lld ",f[i][j][0]+f[i][j][1]-1);
        pf("n");
    }
}

void solve()
{
    int x, y; sf("%d %d",&x,&y);
    if(f[x][y][0])
    {
        LL t = f[x][y][0], s = f[x][y][1];
        f[x][y][0] = f[x][y][1] = 0;
        sum -= s+t-1;
        for(int i = x, j = y+1, k = 1; i <= n && j <= m; k++)
        {
            if(k&1 && f[i][j][1]) f[i][j][1] -= t;
            else if(!(k&1) && f[i][j][0]) f[i][j][0] -= t;
            else break;
            sum -= t;
            if(k&1) i++;
            else j++;
        }
        for(int i = x+1, j = y, k = 1; i <= n && j <= m; k++)
        {
            if( k&1 && f[i][j][0]) f[i][j][0] -= s; 
            else if(!(k&1) && f[i][j][1]) f[i][j][1] -= s;
            else break;
            sum -= s;
            if(k&1) j++;
            else i++;
        }
    }
    else
    {
        LL t = f[x-1][y][1] + 1;
        LL s = f[x][y-1][0] + 1;
        f[x][y][0] = t;
        f[x][y][1] = s;
        sum += s+t-1;
        for(int i = x, j = y+1, k = 1; i <= n && j <= m; k++)
        {
            if(k&1 && f[i][j][1]) f[i][j][1] += t;
            else if(!(k&1) && f[i][j][0]) f[i][j][0] += t; 
            else break;
            sum += t;
            if(k&1) i++;
            else j++;
        }
        for(int i = x+1, j = y, k = 1; i <= n && j <= m; k++)
        {
            if(k&1 && f[i][j][0]) f[i][j][0] += s; 
            else if(!(k&1) && f[i][j][1]) f[i][j][1] += s;
            else break;
            sum += s;
            if(k & 1) j++;
            else i++;
        }
    }
    printf("%lldn",sum);
    // show();
}

int main()
{
    sf("%lld %lld %lld",&n,&m,&q);
    sum = 0;
    qf(i, 1, n) qf(j, 1, m) 
    {
        f[i][j][0] = f[i-1][j][1] + 1;
        f[i][j][1] = f[i][j-1][0] + 1;
        sum += f[i][j][0] + f[i][j][1] - 1;
    }
    // cout << sum << endl;
    while(q--) solve();
    // system("pause");
}

F. RBS

分析:

考虑dp.

记 d p [ t ] dp[t] dp[t]为以t为压缩状态(即, t的第i位是否为1表示第i个字符串有没有被使用), 所有包含在t状态的字符串收尾相连 ,最多的RBS前缀个数.

显然 d p [ 0 ] = 0 dp[0] = 0 dp[0]=0

记 δ [ i ] delta[i] δ[i] 为第i个字符串的左括号数减去右括号数.

记 m i n _ δ [ i ] min_delta[i] min_δ[i] 为第i个字符串中所有前缀中最小的左括号数减去右括号数.

记 a [ i ] [ j ] a[i][j] a[i][j] 为第i个字符串的所有( (左括号数-右括号数) = j ) 的前缀的编号集合.

关于前缀的编号, 不妨以其结束的字符的下标做为其编号.

考虑我们dp到状态 t t t时, 记集合 T T T表示状态t所使用的字符串, d i f dif dif表示集合T所有字符串的左括号数减右括号数的和.

值得注意的是, 我们对dp[t]的定义是, 使用在集合T中所有的字符串按照任意可能的顺序相连, 最多的RBS前缀的个数.

特别的, 我们要使用dp[t]去更新下一个状态, 所以dp[t]所代表的相连字符串应该符合任意前缀的左括号数减右括号数不小于0.

否则, 无论在状态t所代表的字符串添加任何字符串都无法更新答案.

因此, 我们拿一个不属于集合 T T T的字符串 s i s_i si去尝试更新状态t的后继时, 有两种情况:

新构造的相连字符串依然符合 任意前缀的左括号数减右括号数不小于0 的性质, 那么更新状态 d p [ t ∣ 2 i ] dp[t|2^i] dp[t∣2i]
新构造的相连字符串不符合上述性质, 那么 d p [ t ] + s i 的贡献 dp[t]+s_i的贡献 dp[t]+si的贡献是一种可行答案, 更新答案, 但不更新状态.

也就是说我们从状态 t = 0 t= 0 t=0开始dp, 最后中途算出的答案和 d p [ 2 n − 1 ] dp[2^n-1] dp[2n−1]中的最大者为最终答案.

用数学归纳法不难证明上述每一步的正确性.

算法复杂度为 O ( m + 2 n n l o g m ) O(m+2^nnlogm) O(m+2nnlogm), 其中 m = ∑ l e n ( s i ) m = sum len(s_i) m=∑len(si)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define close(); 	ios::sync_with_stdio(false);
#define endl "n"
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int main()
{
    int n; cin >> n;
    vector s(n);
    vector>> a(n);
    vector del(n);
    vector min_del(n);

    qf(i, 0, n-1) 
    {
        cin >> s[i];
        int len = s[i].size();
        int x = len;
        a[i].resize(len*2+1);
        qf(j, 0, len-1)
        {
            x += (s[i][j]=='('?1:-1);
            a[i][x].push_back(j+1);
            min_del[i] = min(min_del[i], x-len);
        }
        del[i] = x-len;
    }
    vector dp(1<= 0 && x <= 2* s[i].size())
            now += a[i][x].size();
            dp[t | (1<

Educational Codeforces Round 115 (Rated for Div. 2)题解A-F

C/C++/C#相关栏目本月热门文章