「CF1276X」Codeforces Round #606 (Div. 1)

2019年12月24日4,5380

A. As Simple as One and Two

当存在 twone 时，删掉 o 比较好，其它情况下直接删掉 two 中的 w 和 one 中的 n

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
string str;
bool mark[200005];
int main()
{
    int T = read();
    while(T--)
    {
        cin >> str;
        int n = str.length();
        for(int i = 0; i < n; i++)
            mark[i] = 0;
        for(int i = 0; i < n - 4; i++)
        {
            if(str.substr(i, 5) == "twone")
                mark[i + 2] = 1;
        }
        string last = "";
        for(int i = 0; i < n; i++)
            if(!mark[i])
            {
                last += str[i];
                if(last.length() > 3)
                    last = last.substr(1, 3);
                if(last == "two")
                    mark[i - 1] = 1;
                if(last == "one")
                    mark[i - 1] = 1;
            }
        vector<int> ve;
        for(int i = 0; i < n; i++)
            if(mark[i])ve.push_back(i);
        cout << ve.size() << endl;;
        for(int i = 0; i < ve.size(); i++)
            cout << ve[i] + 1 <<' ';
        cout << endl;
    }
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

string str;

bool mark[200005];

int main()

{

int T = read();

while(T--)

{

cin >> str;

int n = str.length();

for(int i = 0; i < n; i++)

mark[i] = 0;

for(int i = 0; i < n - 4; i++)

{

if(str.substr(i, 5) == "twone")

mark[i + 2] = 1;

}

string last = "";

for(int i = 0; i < n; i++)

if(!mark[i])

{

last += str[i];

if(last.length() > 3)

last = last.substr(1, 3);

if(last == "two")

mark[i - 1] = 1;

if(last == "one")

mark[i - 1] = 1;

}

vector<int> ve;

for(int i = 0; i < n; i++)

if(mark[i])ve.push_back(i);

cout << ve.size() << endl;;

for(int i = 0; i < ve.size(); i++)

cout << ve[i] + 1 <<' ';

cout << endl;

}

return 0;

}

B. Two Fairs

把 A B 从图中删掉，答案是只和 A 相连的点个数 * 只和 B 相连的点个数

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, a, b;
int fa[200005];
bool vis[2][200005];
vector<int> ve[200005];
void dfs(int x, int k)
{
    if(vis[k][x])return;
    vis[k][x] = 1;
    for(int i = 0; i < ve[x].size(); i++)
        dfs(ve[x][i], k);
}
int main()
{
    int T = read();
    while(T--)
    {
        n = read(); m = read(); a = read(); b = read();
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        for(int i = 1; i <= m; i++)
        {
            int x = read(), y = read();
            ve[x].push_back(y);
            ve[y].push_back(x);
            if(x == a || y == a || x == b || y == b)
                continue;
        }
        vis[0][b] = vis[1][a] = 1;
        dfs(a, 0);
        dfs(b, 1);
        int tmp = -1, tot1 = 0, tot2 = 0;
        for(int i = 1; i <= n; i++)
        {
            if(i != a && i != b)
            {
                if(vis[1][i] && vis[0][i])
                    continue;
                if(vis[1][i])
                    tot1++;
                else tot2++;
            }
        }            
        cout << (ll)tot1 * tot2 << endl;
        for(int i = 1; i <= n; i++)
        {
            vis[1][i] = vis[0][i] = 0;
            ve[i].clear();
        }
    }
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, a, b;

int fa[200005];

bool vis[2][200005];

vector<int> ve[200005];

void dfs(int x, int k)

{

if(vis[k][x])return;

vis[k][x] = 1;

for(int i = 0; i < ve[x].size(); i++)

dfs(ve[x][i], k);

}

int main()

{

int T = read();

while(T--)

{

n = read(); m = read(); a = read(); b = read();

for(int i = 1; i <= n; i++)

fa[i] = i;

for(int i = 1; i <= m; i++)

{

int x = read(), y = read();

ve[x].push_back(y);

ve[y].push_back(x);

if(x == a || y == a || x == b || y == b)

continue;

}

vis[0][b] = vis[1][a] = 1;

dfs(a, 0);

dfs(b, 1);

int tmp = -1, tot1 = 0, tot2 = 0;

for(int i = 1; i <= n; i++)

{

if(i != a && i != b)

{

if(vis[1][i] && vis[0][i])

continue;

if(vis[1][i])

tot1++;

else tot2++;

}

cout << (ll)tot1 * tot2 << endl;

for(int i = 1; i <= n; i++)

{

vis[1][i] = vis[0][i] = 0;

ve[i].clear();

}

return 0;

}

« 「CF1264X」Codeforces Round #604 (Div. 1) 「CF1280X」Codeforces Round #607 (Div. 1) »

hzwer.com _ Home | http://hzwer.com

「CF1276X」Codeforces Round #606 (Div. 1)

分类目录

热门文章

Myfriends

近期评论