CODE FESTIVAL 2017 qual B

I feel like I should take more contests and think more while doing them. . .

I have been thinking about question C for two hours and have no idea. I am mentally retarded. . .

Title link

I won’t talk about the two water questions AB.

C - 3 Steps

The meaning of the question is to give a connected graph without self-loops and duplicate edges, and then continuously add edges to it. The condition for adding edges is that these two points can be connected by three edges, then these two points can add an edge. Ask how many sides can be added at most.

Actually. . . Think about it in terms of bipartite graphs. . .

Think about it later. . . That makes sense. . .

First of all, this is a connected graph. If it cannot be turned into a bipartite graph, it means there is an odd cycle. Then if you draw it, you will find that any two points can eventually add an edge. The answer is $\frac{n*(n-1)}{2}-m$.

What if it can be turned into a bipartite graph. . . Dyeing black and white is the amount of black * the amount of white - m. . .

int n,m;
int col[maxn];
ll cnt1,cnt2;
vector<int>edge[maxn];

bool dfs(int x,int c)
{
	if(col[x]!=-1)
	{
		return col[x]==c;
	}
	col[x]=c;
	int res=1;
	for(int i=0;i<edge[x].size();i++)
	{
		int nxt=edge[x][i];
		res&=dfs(nxt,1-c);
	}
	return res;
}

void solve()
{
	sa(n),sa(m);
	
	repp(i,1,m)
	{
		int x,y;
		sa(x),sa(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	memset(col,-1,sizeof(col));
	bool res = dfs(1,0);
	repp(i,1,n)
	{
		if(col[i])cnt1++;
		else cnt2++;
	}
	ll ans=-m;
	if(res)
	{
		ans+=cnt1*cnt2;
	}
	else
	{
		ans+=1LL*n*(n-1)/2;
	}
	cout<<ans<<endl;
}

D 101 to 010

The meaning of the question is to give a string and ask for the maximum number of operations to turn 101 into 010.

There are only three situations for the final 1 source:

1:1

2: 111101

3: 101111

In this way, it can be converted into the sum of the substring values ​​of non-overlapping intervals, so that the value of the interval is maximized. Can reach $O(n^2)$.

Situations 2 and 3 above can be preprocessed, and dp can be optimized to $O(n)$.

int n;
char v[maxn];
int val[maxn];
int c[maxn];
int dp[maxn];
vector<int>pos[maxn];
 
void solve()
{
    sa(n);
    scanf("%s",v+1);
    n = strlen(v+1);
    repp(i,1,n)
    {
        val[i] = v[i] - '0';
    }
 
    repp(i,1,n)
    {
        c[i]=val[i];
    }
    int st = -1;
    int flag = 0;
    repp(i,3,n)
    {
        if(c[i]&&flag)
        {
            pos[i].push_back(st);
        }
        else if(c[i] == 1&&c[i-1]==0&&c[i-2]==1)
        {
            flag = 1;
            st = i-2;
            pos[i].push_back(st);
        }
        else
        {
            flag = 0;
            st = -1;
        }
    }
    flag = 0;
    repp(i,1,n)
    {
        c[i] = val[i];
    }
    st = -1;
    for(int i=n-2;i>=1;i--)
    {
 
        if(c[i]&&flag)
        {
            pos[st].push_back(i);
        }
        else if(c[i] == 1&&c[i+1]==0&&c[i+2]==1)
        {
            flag = 1;
            st = i+2;
            pos[st].push_back(i);
        }
        else
        {
            flag = 0;
            st = -1;
        }
    }
    repp(i,3,n)
    {
        dp[i] = dp[i-1];
        rep(k,0,pos[i].size())
        {
            dp[i] = max(dp[i], dp[pos[i][k] - 1] + i - pos[i][k] - 1);
        }
    }
    cout<<dp[n]<<endl;
}