学步园

500pt:

题目连接:http://codeforces.com/problemset/problem/369/A

思路：直接贪心，注意一次只能洗一只碗，一开始以为洗一次能把所有都洗好。。。

代码：

#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
using namespace std;
#define ll long long
int n,m,k;
int input[1010];
int main()
{
    while(cin>>n>>m>>k)
    {
        for(int i=0;i<n;i++)
            cin>>input[i];
        int tempm = m;
        int tempk = k;
        int wash = 0;
        for(int i=0;i<n;i++)
        {
            if(input[i]==1)
            {
                if(tempm>0)
                    tempm--;
                else
                {
                    wash++;
                }
            }
            else
            {
                if(tempk>0)
                    tempk--;
                else if(tempm>0)
                    tempm--;
                else
                {
                    wash++;
                }
            }

        }
        cout<<wash<<endl;
    }
    return 0;
}

1000pt:

题目链接：http://codeforces.com/problemset/problem/369/B

思路：对于前k个，先全部赋值r，在根据sk逐个减1，对后面部分，先全部赋值l,再根据sall-sk逐个加1（比赛时写的比较繁琐，貌似可以直接赋值sk,sall-sk的平均值，再+-1来做）

代码：

#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
using namespace std;
#define ll long long
int n,k,l,r,sall,sk;
int input[1010];
int main()
{
    while(cin>>n>>k>>l>>r>>sall>>sk)
    {
        for(int i=1;i<=n;i++)
        {
            if(i<=k)
                input[i] = r;
            else
                input[i] = l;
        }
        int tempk = r*k-sk;
        if(tempk>k)
        {
            int t = tempk/k;
            for(int i=1;i<=k;i++)
            {
                input[i]-=t;
            }
            tempk%=k;
        }
        for(int i=1;i<=tempk;i++)
        {
            input[i]--;
        }
        int tempn = sall-sk - (n-k)*l;
        if(n!=k)
        {
            int t = tempn/(n-k);
            int rest = tempn-t*(n-k);
            for(int i=k+1;i<=n;i++)
                input[i]+=t;
            for(int i=k+1;i<k+1+rest;i++)
                input[i]++;
        }
        for(int i=1;i<=n;i++)
            cout<<input[i]<<" ";
        cout<<endl;
    }
    return 0;
}

1500pt:

题目链接：http://codeforces.com/problemset/problem/369/C

分析：此题在于构建一棵树，用多个vector数组来记录，然后采用dfs()遍历就行，如果某个节点即其各个子节点都不需要修理，并且它到父节点的权值为2，那么该节点是要修理的。

代码：

#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define ll long long
const int N=100010;
int n,from,to,type;
vector<int > ok[N],path[N],v;
bool dfs(int cur,int parent)
{
	bool needToRepair = 0;
	for(int i=0;i<path[cur].size();i++)
	{
		int next = path[cur][i];
		if(next!=parent)
		{
			bool nextNeedtoRepair = dfs(next,cur);
			if(!nextNeedtoRepair&&ok[cur][i])
			{
				v.push_back(next);
				needToRepair = true;
			}
			if(nextNeedtoRepair)
				needToRepair= true;
		}
	}
	return needToRepair;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		cin>>from>>to>>type;
		path[from].push_back(to);
		path[to].push_back(from);
		ok[from].push_back(type-1);
		ok[to].push_back(type-1);	
	}
	dfs(1,-1);
	cout<<v.size()<<endl;
	for(int i=0;i<v.size();i++)
		cout<<v[i]<<" ";
	cout<<endl;


	return 0;
}