usaco 2019 Jan contest gold

http://www.usaco.org/index.php?page=jan19results 全体的な難易度はそれほど高くありませんが、第1題の問題は分かりにくいです.A:dp+统计解答题意:n个単语,每音节个数为s[i],结尾音节押韵为c[i],求一个m行,每行k个音节的诗,再入力m个大字字母,同一字表示这几行最后的押韵是同的,但不同字母押韻可以同样.何種類の詩を書く方法があることを求めます.dp[i]は、長さがiの場合にどのようなシナリオがあるかを表す.sum[i]で単行の終わりの韻をiとする場合のいくつかの案を表す.sum[i]= ∑ c [ j ] = = i d p [ k − s [ j ] ]\sum_{c[j]==i}{dp[k-s[j]]} ∑c[j]==i​dp[k−s[j]].各アルファベット仮定で出現するx回に対して,その寄与はΣi=1 ns u m[i]xsum_である.{i=1}^{n}{sum[i]^x}Σi=1 n sum[i]x(x=0の場合は統計なし).最後に各貢献を乗じると答えです(貢献は0のアルファベットは統計しません).

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pii pair
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
#define minn(x,y) x=min(x,y)
#define maxx(x,y) x=max(x,y)
using namespace std;
int l[5010],c[5010],cnt[30];
ll dp[5010],sum[5010];
ll mod=1e9+7;
ll fpow(int x,int y)
{
	if(y==1)
	{
		return x;
	}
	if(y==0)
	{
		return 1;
	}
	ll an=fpow(x,y/2);
	if(y%2==0)
	{
		return an*an%mod;
	}
	else
	{
		return an*an%mod*x%mod;
	}
}
int main()
{
	int i,j,k,n,m,x,y,z;
	freopen("poetry.in","r",stdin);
	freopen("poetry.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&l[i],&c[i]);
	}
	string s;
	for(i=0;i<m;i++)
	{
		cin>>s;
		cnt[s[0]-'A']++;
	}
	dp[0]=1;
	for(i=0;i<k;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i+l[j]<k)
			{
				dp[i+l[j]]+=dp[i];
				dp[i+l[j]]%=mod;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		sum[c[i]]+=dp[k-l[i]];
		sum[c[i]]%=mod;
	}
	ll ans=1,an;
	for(i=0;i<26;i++)
	{
		an=0;
		for(j=1;j<=n;j++)
		{
			if(cnt[i]==0)
			{
				continue;
			}
			an+=fpow(sum[j],cnt[i]);
			if(an>=mod)
			{
				an-=mod;
			}
		}
		if(an==0)
		{
			continue;
		}
		ans*=an;
		ans=ans%mod;
	}
	printf("%lld",ans);
}

B:法則+線分の木や木の配列を探して問題を書きます:前のn個の数の1つの配列、毎回最も左の1つの数を右にいくつかの位置を移動することができて、少なくともいくつかの部を聞いて彼を1からnに変えることができて、1種の合法的な方案を出力します.数組のデータを手作業で発見した最小回数は(n−増分接尾辞の最大長)である.この結論から,操作ごとに数ビット右にシフトすることができる.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pii pair
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
#define minn(x,y) x=min(x,y)
#define maxx(x,y) x=max(x,y)
using namespace std;
int a[100010];
struct node
{
	int l,r,x;
}t[400010];
int build(int x,int l,int r)
{
	t[x].l=l;
	t[x].r=r;
	t[x].x=0;
	if(l==r)
	{
		return 0;
	}
	build(x*2,l,(l+r)/2);
	build(x*2+1,(l+r)/2+1,r);
}
int ch(int x,int i)
{
	if(t[x].l==t[x].r)
	{
		t[x].x=1;
		return 0;
	}
	int mid=(t[x].l+t[x].r)/2;
	if(i<=mid)
	{
		ch(x*2,i);
	}
	else
	{
		ch(x*2+1,i);
	}
	t[x].x++;
}
int ask(int x,int l,int r)
{
	if(t[x].l>r||t[x].r<l)
	{
		return 0;
	}
	if(t[x].l>=l&&t[x].r<=r)
	{
		return t[x].x;
	}
	int mid,ans=0;
	mid=(t[x].l+t[x].r)/2;
	if(l<=mid)
	{
		ans+=ask(2*x,l,r);
	}
	if(r>=mid+1)
	{
		ans+=ask(2*x+1,l,r);
	}
	return ans;
}
int main()
{
	int i,j,k,n,m,x,y;
	freopen("sleepy.in","r",stdin);
	freopen("sleepy.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(i=n-2;i>=0;i--)
	{
		ch(1,a[i+1]);
		if(a[i]>a[i+1])
		{
			break;
		}
	}
	j=i+1;
	k=j-1;
	printf("%d
",j);
	for(i=0;i<j;i++)
	{
		if(i>0)
		{
			printf(" ");
		}
		printf("%d",k+ask(1,1,a[i]));
		k--;
		ch(1,a[i]);
	}
}

C:最短题意:n个点m条带权无向辺,每点都有c[i]个牛,每牛会走最短絡到点1,道のり等しい会走番号小的点.総時間は牛1頭あたりの時間を合わせます.今、長さtの道を勝手に追加して、最大どれだけの総時間を短縮できるかを聞くことができます.見ると、この辺は必ず1つの点と点1の間に加算されていることがわかります.各点から1までの距離と各点を通る牛の数を算出し、毎回最大値をとり、最後と0は最大値(加算しない辺)をとることができます.各点が通過した牛の数を計算すると、まずx点にある牛を求めることができ、次はどこへ行きますか.これは最短でついでに求めることができますが、注意経路が同じ場合は番号が小さい優先です.そしてn 2暴力は、点ごとに通過する牛の数を求め、答えを統計する.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pii pair
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
#define minn(x,y) x=min(x,y)
#define maxx(x,y) x=max(x,y)
using namespace std;
int to[10010],e[10010];
ll d[10010],ez[10010];
vector<pii> ve[10010];
queue<int> q;
bool vis[10010];
int main()
{
	int i,j,k,n,m,x,y,z,t;
	freopen("shortcut.in","r",stdin);
	freopen("shortcut.out","w",stdout);
	scanf("%d%d%d",&n,&m,&t);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&e[i]);
	}
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ve[x].push_back(mp(y,z));
		ve[y].push_back(mp(x,z));
	}
	memset(d,0x3f,sizeof(d));
	q.push(1);
	d[1]=0;
	vis[1]=1;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(i=0;i<ve[x].size();i++)
		{
			y=ve[x][i].fi;
			if(d[y]==d[x]+ve[x][i].se&&to[y]>x)
			{
				to[y]=x;
			}
			if(d[y]>d[x]+ve[x][i].se)
			{
				d[y]=d[x]+1ll*ve[x][i].se;
				to[y]=x;
				if(!vis[y])
				{
					q.push(y);
					vis[y]=1;
				}
			}
		}
		vis[x]=0;
	}
	for(i=2;i<=n;i++)
	{
		x=i;
		while(x>1)
		{
			ez[x]+=1ll*e[i];
			x=to[x];
		}
	}
	ll ans=0;
	for(i=2;i<=n;i++)
	{
		ans=max(ans,(d[i]-1ll*t)*ez[i]);
	}
	printf("%lld",ans);
}