ACM-ICPC 2018 焦作赛区网络预赛 wu-kan

Magic Mirror

#include <cstdio>
#include <cstring>
int T;
char s[20],a[20]="JESSIE",b[20]="jessie";
bool o;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%s",s);
		if (strlen(s)!=6)
		{
			printf("Dare you say that again?\n");
			continue;
		}
		o=true;
		for (int i=0;i<6;i++)
		 if ((s[i]!=a[i])&&(s[i]!=b[i]))
		 {
		 	o=false;
		 	break;
		 }
		if (o) printf("Good guy!\n");
		 else printf("Dare you say that again?\n");
	}
	return 0;
}

Mathematical Curse

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t,n,m,k;
long long a[1010];
char s[10];
long long mx[1010][10],mn[1010][10];
int main()
{
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d%d",&n,&m,&k);
		for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
		scanf("%s",s);
		memset(mx,0,sizeof(mx));
		memset(mn,0,sizeof(mn));
		mx[0][0]=mn[0][0]=k;
		for (int i=1;i<=n;i++)
		 for (int j=1;(j<=m)&&(j<=i);j++)
		 {
		 	mx[i][0]=mn[i][0]=k;
		  	if (s[j-1]=='+') mx[i][j]=mx[i-1][j-1]+a[i],mn[i][j]=mn[i-1][j-1]+a[i];
		   	 else if (s[j-1]=='-') mx[i][j]=mx[i-1][j-1]-a[i],mn[i][j]=mn[i-1][j-1]-a[i];
		      else if (s[j-1]=='*')
			  {
			  	if (a[i]>=0) mx[i][j]=mx[i-1][j-1]*a[i],mn[i][j]=mn[i-1][j-1]*a[i];
			  	 else mx[i][j]=mn[i-1][j-1]*a[i],mn[i][j]=mx[i-1][j-1]*a[i];
			  }
			   else
			   {
			   	if (a[i]>=0) mx[i][j]=mx[i-1][j-1]/a[i],mn[i][j]=mn[i-1][j-1]/a[i];
			   	 else mx[i][j]=mn[i-1][j-1]/a[i],mn[i][j]=mx[i-1][j-1]/a[i];
			   }
			if (i>j) mx[i][j]=max(mx[i][j],mx[i-1][j]),mn[i][j]=min(mn[i][j],mn[i-1][j]);
		 }
		printf("%lld\n",mx[n][m]);
	}
	return 0;
}

Password


Sequence


Jiu Yuan Wants to Eat

链剖+双标记维护区间和,区间取反操作等价于区间乘 -1 后区间加 -1 。 时限卡的有点紧,线段树用 vector 建的时候卡时限 2832ms/3000ms,改成数组也要跑 2448ms/3000ms。

#include<cstdio>
#include<vector>
using namespace std;
typedef unsigned long long ll;
struct SegmentTree
{
	struct Node
	{
		int l,r;
		ll mul,add,sum;
		void set(ll m,ll a)
		{
			mul*=m,add=add*m+a,sum=sum*m+a*(r-l+1);
		}
		void up(const Node &lc,const Node &rc)
		{
			sum=lc.sum+rc.sum;
		}
		void down(Node &lc,Node &rc)
		{
			lc.set(mul,add),rc.set(mul,add),mul=1,add=0;
		}
	};
	vector<Node> v;
	SegmentTree(int N):v(N<<2)
	{
		build(1,N);
	}
	void build(int l,int r,int rt=1)
	{
		v[rt]= {l,r};
		if(l>=r)return;
		int m=l+r>>1;
		build(l,m,rt<<1),build(m+1,r,rt<<1|1),v[rt].up(v[rt<<1],v[rt<<1|1]);
	}
	void set(int l,int r,ll mul,ll add,int rt=1)
	{
		if(l<=v[rt].l&&v[rt].r<=r)return v[rt].set(mul,add);
		v[rt].down(v[rt<<1],v[rt<<1|1]);
		int m=v[rt].l+v[rt].r>>1;
		if(m>=r)set(l,r,mul,add,rt<<1);
		else if(m<l)set(l,r,mul,add,rt<<1|1);
		else set(l,m,mul,add,rt<<1),set(m+1,r,mul,add,rt<<1|1);
		v[rt].up(v[rt<<1],v[rt<<1|1]);
	}
	Node ask(int l,int r,int rt=1)
	{
		if(l<=v[rt].l&&v[rt].r<=r)return v[rt];
		v[rt].down(v[rt<<1],v[rt<<1|1]);
		int m=v[rt].l+v[rt].r>>1;
		if(m>=r)return ask(l,r,rt<<1);
		if(m<l)return ask(l,r,rt<<1|1);
		return v[0].up(ask(l,m,rt<<1),ask(m+1,r,rt<<1|1)),v[0];
	}
};
struct Graph
{
	struct Vertex
	{
		vector<int> o,i;//相关出边和入边编号
		int siz,dep,top,dfn;//树链剖分中使用,依次代表子树节点数、深度、所在链的顶端节点、dfs序
	};
	typedef pair<int,int> Edge;
	vector<Vertex> v;//点集
	vector<Edge> e;//边集
	Graph(int n):v(n) {}
	void add(const Edge &ed)
	{
		v[ed.first].o.push_back(e.size());
		v[ed.second].i.push_back(e.size());
		e.push_back(ed);
	}
	int ch(int u,int i=0)//u的第i个孩子节点
	{
		return e[v[u].o[i]].second;
	}
	int fa(int u,int i=0)//u的第i个父节点
	{
		return e[v[u].i[i]].first;
	}
};
struct Diagram:Graph
{
	SegmentTree data;
	Diagram(const Graph &g,int root):
		Graph(g.v.size()),data(g.v.size())
	{
		int cnt=v[root].dfn=v[root].dep=1;
		build(root,g),dfs(v[root].top=root,cnt);
	}
	void build(int u,const Graph &g)//无向图dfs建树,且重边在最前,u为根节点
	{
		v[u].siz=1;
		for(int i=0,k,to; i<g.v[u].o.size(); ++i)
			if(k=g.v[u].o[i],to=g.e[k].second,!v[to].siz)//没访问过的点siz默认0
			{
				build(to,g),v[u].siz+=v[to].siz,add(g.e[k]);
				if(v[ch(u)].siz<v[to].siz)//重边移到最前
					swap(v[u].o.front(),v[u].o.back());
			}
	}
	void dfs(int u,int &cnt)
	{
		for(int i=0,to; i<v[u].o.size(); ++i)
		{
			v[to=ch(u,i)].dep=v[u].dep+1;
			v[to].top=i?to:v[u].top;
			v[to].dfn=++cnt;
			dfs(to,cnt);
		}
	}
	void set(int x,int y,ll mul,ll add)
	{
		for(; v[x].top!=v[y].top; x=fa(v[x].top))
		{
			if(v[v[x].top].dep<v[v[y].top].dep)swap(x,y);
			data.set(v[v[x].top].dfn,v[x].dfn,mul,add);
		}
		if(v[x].dep<v[y].dep)swap(x,y);
		data.set(v[y].dfn,v[x].dfn,mul,add);
	}
	SegmentTree::Node ask(int x,int y)
	{
		SegmentTree::Node ans;
		for(ans.sum=0; v[x].top!=v[y].top; x=fa(v[x].top))
		{
			if(v[v[x].top].dep<v[v[y].top].dep)swap(x,y);
			ans.up(ans,data.ask(v[v[x].top].dfn,v[x].dfn));
		}
		if(v[x].dep<v[y].dep)swap(x,y);
		return ans.up(ans,data.ask(v[y].dfn,v[x].dfn)),ans;
	}
};
int main()
{
	for(int n; ~scanf("%d",&n);)
	{
		Graph g(n+1);
		for(int i=2,b; i<=n; ++i)
			scanf("%d",&b),g.add({b,i});
		Diagram d(g,1);
		scanf("%d",&n);
		for(int i=0,u,v; i<n; ++i)
		{
			ll x;
			scanf("%llu%d%d",&x,&u,&v);
			if(x==1)scanf("%llu",&x),d.set(u,v,x,0);
			else if(x==2)scanf("%llu",&x),d.set(u,v,1,x);
			else if(x==3)d.set(u,v,-1,-1);
			else printf("%llu\n",d.ask(u,v).sum);
		}
	}
}

Modular Production Line

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=100009,NPOS=-1,INF=1e18;
struct Ranker:vector<ll>
{
	void init()
	{
		sort(begin(),end()),resize(unique(begin(),end())-begin());
	}
	int ask(ll x)const
	{
		return lower_bound(begin(),end(),x)-begin();
	}
};
struct Graph
{
	struct Vertex
	{
		vector<int> a/*,b*/;//相关出边和入边编号
		//int siz,dep,top,dfn;//树链剖分中使用,依次代表子树节点数、深度、所在链的顶端节点、dfs序
	};
	struct Edge
	{
		int from,to;
		ll dist,cap;//边长、容量,图论算法使用
	};
	vector<Vertex> v;//点集
	vector<Edge> e;//边集
	Graph(int n):v(n) {}
	void add(const Edge &ed)
	{
		if(ed.from==ed.to)return;//如果有需要请拆点
		v[ed.from].a.push_back(e.size());
		//v[ed.to].b.push_back(e.size());
		e.push_back(ed);
	}
};
struct EdmondKarp:Graph
{
	ll flow,cost;
	vector<ll> f;
	EdmondKarp(int n):Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.from,ed.to),ed.cap=0,ed.dist*=-1;
		Graph::add(ed);
	}
	void ask(int s,int t)
	{
		vector<int> p(v.size(),NPOS);
		for(f.assign(e.size(),flow=cost=0);;)
		{
			vector<ll> d(v.size(),INF);
			vector<int> flag(v.size(),d[s]=0);
			for(deque<int> q(flag[s]=1,s); !q.empty(); q.pop_front())
				for(int u=q.front(),i=flag[u]=0,k,to; i<v[u].a.size(); ++i)
					if(k=v[u].a[i],to=e[k].to,
					        e[k].cap>f[k]&&d[to]>d[u]+e[k].dist)
					{
						d[to]=d[u]+e[k].dist,p[to]=k;
						if(!flag[to])q.push_back(to),flag[to]=1;
					}
			if(d[t]==INF)return;
			ll _f=INF;
			for(int u=t; u!=s; u=e[p[u]].from)
				_f=min(_f,e[p[u]].cap-f[p[u]]);
			for(int u=t; u!=s; u=e[p[u]].from)
				cost+=_f*e[p[u]].dist,f[p[u]]+=_f,f[p[u]^1]-=_f;
			flow+=_f;
		}
	}
};
int t,n,m,k,x[N],y[N],w[N];
int main()
{
	for(scanf("%d",&t); t--;)
	{
		Ranker rk;
		scanf("%d%d%d",&n,&k,&m);
		for(int i=0; i<m; ++i)
		{
			scanf("%d%d%d",&x[i],&y[i],&w[i]);
			rk.push_back(x[i]);
			rk.push_back(++y[i]);
		}
		rk.init();
		EdmondKarp g(rk.size()+2);
		for(int i=0; i<rk.size(); ++i)g.add({i,i+1,0,k});
		for(int i=0; i<m; ++i)g.add({rk.ask(x[i]),rk.ask(y[i]),-w[i],1});
		g.add({rk.size()+1,0,0,k});
		g.ask(rk.size()+1,rk.size());
		printf("%lld\n",-g.cost);
	}
}

Give Candies

答案是$2^{n-2}$,用费马小定理把指数对 M-1 取模后进行运算避免更多的高精度运算。

#include<stdio.h>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
typedef int ll;
const ll M=1e9+7;
ll pow(ll a,ll b,ll m)
{
	ll r=1;
	for(a%=m; b; b>>=1,a=mul(a,a,m))
		if(b&1)r=mul(r,a,m);
	return r;
}
char s[100009];
int t,n;
int main()
{
	for(scanf("%d",&t); t--;)
	{
		scanf("%s",s);
		for(int i=n=0; s[i]; ++i)
			n=mul(n,10,M-1)+s[i]-'0';
		printf("%d\n",pow(2,n+M-2,M));
	}
}

String and Times

拉一个后缀数组的板子跑掉了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
struct SufArr
{
	vector<int> sa,rk,h;
	SufArr(const vector<int> &s,int m):sa(s.size(),0),rk(s),h(s.size(),0)
	{
		vector<int> cnt(s.size()+m,0);
		for(int i=0; i<s.size(); ++i)++cnt[rk[i]];
		for(int i=1; i<m; ++i)cnt[i]+=cnt[i-1];
		for(int i=0; i<s.size(); ++i)sa[--cnt[rk[i]]]=i;
		for(int k=1,j=0; k<=s.size()&&j<s.size()-1; k<<=1)
		{
			for(int i=0; i<s.size(); ++i)
			{
				if(j=sa[i]-k,j<0)j+=s.size();
				h[cnt[rk[j]]++]=j;
			}
			cnt[0]=sa[h[0]]=j=0;
			for(int i=1; i<s.size(); ++i)
			{
				if(rk[h[i]]!=rk[h[i-1]]||rk[h[i]+k]!=rk[h[i-1]+k])
					cnt[++j]=i;
				sa[h[i]]=j;
			}
			swap(rk,sa),swap(sa,h);
		}
		for(int i=0,k=0,j=rk[0]; i<s.size()-1; ++i,++k)
			for(; ~k&&s[i]!=s[sa[j-1]+k]; j=rk[sa[j]+1],--k)
				h[j]=k;
	}
};
struct SparseTable
{
	typedef int ll;
	vector<vector<ll> > f;
	SparseTable(const vector<ll> &a):f(log2(a.size())+1,a)
	{
		for(int k=0; k+1<f.size(); ++k)
			for(int i=0; i+(1<<k)<a.size(); ++i)
				f[k+1][i]=min(f[k][i],f[k][i+(1<<k)]);
	}
	ll ask(int l,int r)
	{
		int k=log2(r-l+1);
		return min(f[k][l],f[k][r+1-(1<<k)]);
	}
};
ll cal(SufArr &sa,SparseTable &st,int k)//原串中至少出现k次的子串数量
{
	ll ans=0;
	if(k>1)
		for(int l=2,r=k; r<sa.h.size(); ++l,++r)
			ans+=max(st.ask(l,r)-sa.h[l-1],0);
	else
		for(int i=1; i<sa.h.size(); ++i)
			ans+=sa.h.size()-1-sa.sa[i]-sa.h[i];
	return ans;
}
char s[2000009];
int main()
{
	for(int a,b; ~scanf("%s%d%d",s,&a,&b);)
	{
		SufArr sa(vector<int>(s,s+strlen(s)+1),'Z'+1);
		SparseTable st(sa.h);
		printf("%lld\n",cal(sa,st,a)-cal(sa,st,b+1));
	}
}

Save the Room

#include<stdio.h>
int main()
{
	for(int a,b,c; ~scanf("%d%d%d",&a,&b,&c);)
		printf(a%2&&b%2&&c%2?"No\n":"Yes\n");
}

Participate in E-sports

交了个高精度开根号上去。

#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
struct Wint:vector<int>//继承vector
{
	static const int width=9,base=1e9;
	Wint(unsigned long long n=0)//普通初始化,当整型数和Wint同时运算时会提升至Wint
	{
		for(; n; n/=base)push_back(n%base);
	}
	explicit Wint(const string &s)//字符串初始化函数,未判断字符串合法情况
	{
		for(int len=int(s.size()-1)/width+1,b,e,i=0; i<len; ++i)
			for(e=s.size()-i*width,b=max(0,e-width),push_back(0); b!=e; ++b)
				back()=back()*10+s[b]-'0';
		trim(0);
	}
	Wint& trim(bool up=1)//去前导0,是否需要进位,很常用的小函数,为方便返回自身
	{
		for(int i=1; up&&i<size(); ++i)
		{
			if((*this)[i-1]<0)--(*this)[i],(*this)[i-1]+=base;
			if((*this)[i-1]>=base)(*this)[i]+=(*this)[i-1]/base,(*this)[i-1]%=base;
		}
		while(!empty()&&back()<=0)pop_back();
		for(; up&&!empty()&&back()>=base; (*this)[size()-2]%=base)
			push_back(back()/base);
		return *this;
	}
	friend istream& operator>>(istream &is,Wint &n)
	{
		string s;//懒
		return is>>s,n=Wint(s),is;
	}
	friend ostream& operator<<(ostream &os,const Wint &n)
	{
		if(n.empty())return os.put('0');
		os<<n.back();
		char ch=os.fill('0');
		for(int i=n.size()-2; ~i; --i)
			os.width(n.width),os<<n[i];
		return os.fill(ch),os;
	}
	friend bool operator<(const Wint &a,const Wint &b)
	{
		if(a.size()!=b.size())return a.size()<b.size();
		for(int i=a.size()-1; ~i; --i)
			if(a[i]!=b[i])return a[i]<b[i];
		return 0;
	}
	friend bool operator>(const Wint &a,const Wint &b)
	{
		return b<a;
	}
	friend bool operator<=(const Wint &a,const Wint &b)
	{
		return !(a>b);
	}
	friend bool operator>=(const Wint &a,const Wint &b)
	{
		return !(a<b);
	}
	Wint& operator+=(const Wint &b)
	{
		if(size()<b.size())resize(b.size());//保证有足够的位数
		for(int i=0; i<b.size(); ++i)(*this)[i]+=b[i];
		return trim();//单独进位防自运算
	}
	friend Wint operator+(Wint a,const Wint &b)
	{
		return a+=b;
	}
	Wint& operator++()//前置版本
	{
		return *this+=1;//懒
	}
	Wint operator++(int)//后置版本
	{
		Wint b(*this);
		return ++*this,b;
	}
	Wint& operator-=(const Wint &b)//a<b会使a变为0
	{
		if(size()<b.size())resize(b.size());//保证有足够的位数
		for(int i=0; i<b.size(); ++i)(*this)[i]-=b[i];
		return trim();//单独进位防自运算
	}
	friend Wint operator-(Wint a,const Wint &b)
	{
		return a-=b;
	}
	Wint& operator--()//前置版本
	{
		return *this-=1;//懒
	}
	Wint operator--(int)//后置版本
	{
		Wint b(*this);
		return --*this,b;
	}
	Wint& operator*=(const Wint &b)//高精度乘法,常规写法
	{
		Wint c;
		c.assign(size()+b.size(),0);
		for(int j=0,k,l; j<b.size(); ++j)
			if(b[j])//稀疏优化,特殊情况很有效
				for(int i=0; i<size(); ++i)
				{
					unsigned long long n=(*this)[i];
					for(n*=b[j],k=i+j; n; n/=base)
						c[k++]+=n%base;
					for(l=i+j; c[l]>=base||l+1<k; c[l++]%=base)
						c[l+1]+=c[l]/base;
				}
		return swap(c),trim(0);
	}
	/*
	Wint& operator*=(const Wint &b)//一种效率略高但对位宽有限制的写法
	{
		vector<unsigned long long> n(size()+b.size(),0);//防爆int
		//乘法算完后统一进位效率高,防止乘法溢出(unsigned long long范围0~1.8e19)
		//位宽为9时size()不能超过18(十进制162位),位宽为8时size()不能超过1800(十进制14400位)等等。
		for(int j=0; j!=b.size(); ++j)
			if(b[j])//稀疏优化,特殊情况很有效
				for(int i=0; i!=size(); ++i)
					n[i+j]+=(unsigned long long)(*this)[i]*b[j];
		for(int i=1; i<n.size(); ++i)//这里用<防止位数0,单独进位防自运算
			n[i]+=n[i-1]/base,n[i-1]%=base;
		return assign(n.begin(),n.end()),trim(0);
	}
	Wint& operator*=(const Wint &b)//fft优化乘法,注意double仅15位有效数字,调小Wint::width不超过2,计算自2*log2(base)+2*log2(len)<53
	{
	    vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
	    ax=FFT(size()+b.size()).ask(ax,bx);
	    for(int i=1; i<ax.size(); ++i)
	        ax[i]+=ax[i-1]/base,ax[i-1]%=base;
	    return assign(ax.begin(),ax.end()),trim(0);
	}
	Wint& operator*=(const Wint &b)//ntt优化,Wint::width不超过2
	{
	    vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
	    ax=FNTT(size()+b.size(),(7<<26)+1,3).ask(ax,bx);
	    for(int i=1; i<ax.size(); ++i)
	        ax[i]+=ax[i-1]/base,ax[i-1]%=base;
	    return assign(ax.begin(),ax.end()),trim(0);
	}
	*/
	friend Wint operator*(Wint a,const Wint &b)
	{
		return a*=b;
	}
	Wint& operator/=(Wint b)
	{
		Wint r,c,d=b.base/(b.back()+1);
		*this*=d,b*=d,c.assign(size(),0);
		for(int i=size()-1; ~i; --i)
		{
			r.insert(r.begin(),(*this)[i]);
			unsigned long long s=0;
			for(int j=b.size(); j+1>=b.size(); --j)//b.size()==0肯定第一行就出问题的
				s=s*b.base+(j<r.size()?r[j]:0);
			for(d=c[i]=s/b.back(),d*=b; r<d; r+=b)--c[i];
			r-=d;
		}
		return swap(c),trim(0);//r为加倍后的余数,可通过高精度除低精度得到真正余数,此处略
	}
	friend Wint operator/(Wint a,const Wint &b)
	{
		return a/=b;
	}
	Wint& operator%=(const Wint &b)
	{
		return *this-=*this/b*b;
	}
	friend Wint operator%(Wint a,const Wint &b)
	{
		return a%=b;
	}
//开平方,改自ZJU模板
	bool cmp(long long c,int d,const Wint &b)const
	{
		if((int)b.size()-(int)size()<d+1&&c)return 1;
		long long t=0;
		for(int i=b.size()-1,lo=-(base<<1); lo<=t&&t<=0&&~i; --i)
			if(t=t*base-b[i],0<=i-d-1&&i-d-1<size())
				t+=(*this)[i-d-1]*c;
		return t>0;
	}
	Wint& sub(const Wint &b,long long k,int d)
	{
		int l=b.size()+d;
		for(int i=d+1; i<=l; ++i)
		{
			long long tmp=(*this)[i]-k*b[i-d-1];
			if(tmp<0)
			{
				(*this)[i+1]+=(tmp-base+1)/base;
				(*this)[i]=tmp-(tmp-base+1)/base*base;
			}
			else (*this)[i]=tmp;
		}
		for(int i=l+1; i<size()&&(*this)[i]<0; ++i)
		{
			(*this)[i+1]+=((*this)[i]-base+1)/base;
			(*this)[i]-=((*this)[i]-base+1)/base*base;
		}
		return trim(0);
	}
	friend Wint sqrt(Wint a)
	{
		Wint n;
		n.assign(a.size()+1>>1,0);
		for(int i=n.size()-1,l,r; ~i; --i)
		{
			for(l=0,r=a.base,n[i]=l+r>>1; r-l>1; n[i]=l+r>>1)
			{
				if(n.cmp(n[i],i-1,a))r=n[i];
				else l=n[i];
			}
			a.sub(n,n[i],i-1),n[i]+=l+r>>1;
		}
		for(int i=0; i<n.size(); ++i)n[i]>>=1;
		return n.trim(0);
	}
	/*
	friend Wint sqrt(const Wint &a)//常规牛顿迭代实现的开平方算法,慢但是好敲
	{
	    Wint b=a,c=(b+1)/2;
	    while(b!=c)swap(b,c),c=(b+a/b)/2;
	    return c;
	}
	friend Wint sqrt(const Wint &a)
	{
	    Wint ret,t;
	    ret.assign((a.size()+1)>>1,0);
	    for(int i=ret.size()-1,l,r; ~i; --i)
	    {
	        for(l=0,r=a.base; r-l>1;)
	        {
	            ret[i]=l+(r-l)/2;
	            t=ret*ret;
	            if(a<t)r=ret[i];
	            else l=ret[i];
	        }
	        if(!l&&i==ret.size()-1)ret.pop_back();
	        else ret[i]=l;
	    }
	    return ret;
	}
	*/
};
int check(Wint n)
{
	Wint sn=sqrt(n);
	return sn*sn==n;
}
int main()
{
	int t;
	for(cin>>t; t--;)
	{
		Wint n;
		cin>>n;
		int ans=check(n)*2+check(n*(n-1)/2);
		cout<<(ans==0?"League of Legends\n":
		       ans==1?"Clash Royale\n":
		       ans==2?"Hearth Stone\n":
		       "Arena of Valor\n");
	}
}

Transport Ship

拆成 01 背包。

#include<stdio.h>
#include<string.h>
const int N=511,S=32767>>1,M=1e9+7;
int t,n,q,m,v[N],f[N][S];
int main()
{
	for(scanf("%d",&t); t--;)
	{
		scanf("%d%d",&n,&q);
		for(int i=m=0,V,C; i<n; ++i)
		{
			scanf("%d%d",&V,&C);
			for(int i=0; i<C; ++i)
				v[++m]=(1<<i)*V;
		}
		for(int i=f[0][0]=1; i<=m; ++i)
			for(int s=0; s<S; ++s)
				if(f[i][s]=f[i-1][s],s>=v[i])
					f[i][s]=(f[i][s]+f[i-1][s-v[i]])%M;
		for(int i=0,s; i<q; ++i)
		{
			scanf("%d",&s);
			printf("%d\n",f[m][s]);
		}
	}
}

Poor God Water

矩阵乘一下。

#include<cstdio>
#include<algorithm>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
using namespace std;
typedef long long ll;
const ll N=9,M=1e9+7;
struct Matrix
{
	static int n;
	ll a[N][N];
	Matrix(ll k=0)
	{
		for(int i=0; i<n; ++i)fill(a[i],a[i]+n,0),a[i][i]=k;
	}
	ll* operator[](int n)
	{
		return a[n];
	}
};
int Matrix::n=N;
Matrix operator*(const Matrix &a,const Matrix &b)
{
	Matrix r(0);
	for(int i=0; i<r.n; ++i)
		for(int j=0; j<r.n; ++j)
			for(int k=0; k<r.n; ++k)
				r.a[i][j]=(r.a[i][j]+mul(a.a[i][k],b.a[k][j],M))%M;
	return r;
}
Matrix pow(Matrix a,ll b)
{
	Matrix r(1);
	for(; b; b>>=1,a=a*a)
		if(b&1)r=r*a;
	return r;
}
int main()
{
	ll t,n,ans;
	for(scanf("%lld",&t); t--;)
	{
		scanf("%lld",&n);
		if(n<3)
		{
			printf("%d\n",n==1?3:9);
			continue;
		}
		Matrix A,P;
		for(int i=0; i<N; ++i)A[i][0]=1;
		P[0][3]=P[0][6]=1;
		P[1][0]=P[1][3]=P[1][6]=1;
		P[2][0]=P[2][3]=1;
		P[3][1]=P[3][4]=P[3][7]=1;
		P[4][1]=P[4][7]=1;
		P[5][1]=P[5][4]=1;
		P[6][5]=P[6][8]=1;
		P[7][2]=P[7][8]=1;
		P[8][2]=P[8][5]=1;
		A=pow(P,n-2)*A;
		for(int i=ans=0; i<N; ++i)ans=(ans+A[i][0])%M;
		printf("%lld\n",ans);
	}
}