Weekly Training Farm 23

比賽連結：Weekly Training Farm 23

A：優先隊列亂搞：

#include<bits\stdc++.h>
using namespace std;
typedef long long ll;
struct cmp
{
	bool operator () (const ll a,const ll b)
	{
		return a>b;
	}
};
int main()
{
	int n;
	while(cin>>n)
	{
		priority_queue<ll,vector<ll>,cmp> q;
		ll sum=0,t;
		int ans=0;
		for(int i=0;i<n;i++)
		{
			cin>>t;
			sum+=t;
			if(t<0)	q.push(t);
			if(sum<0)
			{
				ll tmp=q.top();q.pop();
				ans++;
				sum-=tmp;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
           

B：二分檢驗

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double a[1007];
int n;double x;
bool check(double t)
{
	double res=0;
	for(int i=0;i<n;i++)
	{
		if(t<a[i])	res+=a[i]-t;
	}
	return res>=x;
}
int main()
{
	while(cin>>n)
	{
		double l=0,r=0;
		for(int i=0;i<n;i++)	cin>>a[i],r=max(r,a[i]);
		cin>>x;
		int cnt=5;
		while(r-l>=1e-13)
		{
			double mid=(r+l)/2;
			if(check(mid))	l=mid;
			else r=mid;
		}
		printf("%.15lf\n",r);
	}
	return 0;
}
           

C：簡單dp，dp[i][j]表示第i位，數字填j時有多少種方案。狀态轉移非常容易。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
const ll mod=1e9+7;
ll dp[maxn][10];
int main()
{

	ios::sync_with_stdio(false);
	string s;
	while(cin>>s)
	{
		memset(dp,0,sizeof(dp));
		if(s[0]=='?')	for(int i=0;i<=9;i++)	dp[0][i]=1;
		else dp[0][s[0]-'0']=1;
		for(int i=1;i<s.length();i++)
			for(int j=(s[i]=='?'?0:s[i]-'0');j<=(s[i]=='?'?9:s[i]-'0');j++)
				for(int k=0;k<=j;k++)
					dp[i][j]=(dp[i-1][k]+dp[i][j])%mod;
		ll ans=0;
        for(int i=0;i<=9;i++)	ans=(ans+dp[s.length()-1][i])%mod;
        cout<<ans<<endl;
	}
	return 0;
}
           

E：dfs搜一下，若某棵子樹是三個結點，那麼這三個結點顯然是一組，否則dfs傳回這課子樹的結點數，當一棵子樹的結點數大于3時，顯然不能合并。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+7;
vector<int> adj[maxn];
bool vis[maxn];
int n;
bool flag;
int dfs(int u)
{

	vis[u]=true;
	int res=1;
	for(int i=0;i<adj[u].size();i++)
	{
		int next=adj[u][i];
		//if(cnt-->0)	printf("%d %d\n",u,next);
		if(vis[next])	continue;
		res+=dfs(next);
		if(!flag)	return flag;
	}
	if(res>3)
	{
		return flag=false;
	}
	return res%3;
}
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n)
	{
		n*=3;
		for(int i=1;i<=n;i++)	adj[i].clear();
		int u,v;
		flag=true;
		for(int i=1;i<n;i++)
		{
			cin>>u>>v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		memset(vis,0,sizeof(vis));
		dfs(1);
		if(flag)	cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}