第十八届浙江大学宁波理工学院程序设计大赛（同步赛）

• 目录
• • A minimum
  • • 知识点
    • 题目代码
  • B match
  • • 知识点
    • 题目代码
  • C accept
  • • 知识点
    • 题目代码
  • D triangle
  • • 知识点
    • 题目代码
  • E candy-easy
  • • 知识点
    • 题目代码
  • F candy-hard
  • • 知识点
    • 题目代码
  • G wave
  • • 知识点
    • 题目代码
  • H communication
  • • 知识点
    • 题目代码
• 结语

简单思维

#include
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
const ll mod=1e9+7;
ll t;
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res%mod;
}
map mp;
int main(){
	scanf("%lld",&t);
	while(t--){
		ll x;
		scanf("%lld",&x);
		mp.clear();
		ll mi=x;
		while(1){
			mp[x]=1;
			ll s=x;
			ll sum=0;
			while(s){
				sum+=s%10;
				s/=10;
			}
			s=x;
			ll nx=0,ny=0;
			if(sum%2==1){
				nx=sum/2;
				ny=sum/2+1;
			}else{
				nx=ny=sum/2;
			}
			x=qpow(ny,nx);
			//cout< 
B match 
知识点 
利用01的个数进行匹配
 
题目代码 
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
const ll mod=1e9+7;
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res%mod;
}
ll n;
ll s[maxn];
ll t;
map mp;
void chuli(ll x,ll id){
	ll sum0=0;
	ll sum1=0;
	while(x){
		if(x&1)sum1++;
		else sum0++;
		x>>=1;
	}
	s[id]=sum1-sum0;
	mp[s[id]]++;
}
ll gcd(ll x,ll y){
	return y ? gcd(y,x%y) : x;
}
int main(){
	scanf("%lld",&t);
	while(t--){
		mp.clear();
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			ll x;
			scanf("%lld",&x);
			chuli(x,i);
		}
		//sort(s+1,s+1+n);
		ll ans=0;
		for(int i=1;i<=n;i++){
			ll val=s[i];
			ans+=mp[1-val];
			ans+=mp[-1-val];	
			//cout< 
C accept 
知识点 
签到
 
题目代码 
#include
using namespace std;
int main(){
    cout<<"AC!AC!AC!"< 
D triangle 
知识点 
贪心
 
题目代码 
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
ll n;
ll a[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	ll ans=0;
	ll x=a[1];
	ll y=a[2];
	ll res=0;
	for(int i=3;i<=n;i++){
		if(a[i]>=(x+y)){
			res++;
			x=y;
			y=a[i];
		}
	}
	if(res){
		cout< 
E candy-easy 
知识点 
暴力模拟
 
题目代码 
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll t;
ll n,m;
ll a[maxn],b[maxn];
bool cmp(ll x,ll y){
	return x>y;
}
int main(){
	scanf("%lld",&t);
	while(t--){
		ll ma=1010;
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		for(int i=1;i<=m;i++){
			scanf("%lld",&b[i]);
			//que.push({b[i],i});
		}
		sort(a+1,a+1+n);
		ll flag=1;
		for(int i=n;i>=1;i--){
			sort(b+1,b+1+m,cmp);
			ll val=a[i];
			for(int j=1;j<=m;j++){
				if(b[j]>=1){
					b[j]--;
					val--;
				}else{
					flag=0;
					break;
				}
				if(!val){
					flag=1;
					break;
				}
			}
			if(!flag){
				break;
			}
		}
		if(!flag){
			printf("non");
		}else{
			printf("yesn");
		}
	}
	return 0;
}
 
F candy-hard 
知识点 
差分+贪心
 
题目代码 
#include
using namespace std;
typedef long long int ll;
const ll maxn=5e4+5;
ll n,m,t;
ll a[maxn];
ll b[maxn];
ll vis[maxn*2];
ll cnt[maxn*2];
bool cmp(ll x,ll y){
	return x>y;
}
int main(){
	scanf("%lld",&t);
	while(t--){
		memset(vis,0,sizeof(vis));
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		for(int i=1;i<=m;i++){
			scanf("%lld",&b[i]);
		}
		sort(a+1,a+1+n,cmp);
		ll l=1;
		for(int i=1;i<=m;i++){
			vis[l]++;
			vis[l+b[i]]--;
		}//差分 
		ll sum=0;
		ll flag=0;
		cnt[0]=0;
		for(int i=1;i<=n;i++){
			cnt[i]=cnt[i-1]+vis[i];
			if(cnt[i]+sum>=a[i]){
				sum=cnt[i]+sum-a[i];//剩余的下面还能接着用 
			}else{
				flag=1;
				break;
			}
			//cout< 
G wave 
知识点 
动态规划
 
题目代码 
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
const ll mod=1e9+7;
ll n;
ll a[maxn];
ll dp[maxn][10];
ll t;
int main(){
	scanf("%lld",&t);
	while(t--){
		memset(dp,0,sizeof(dp));
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			dp[i][0]=dp[i][1]=1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;ja[j]){
					dp[i][1]=max(dp[i][1],dp[j][0]+1);
				}else if(a[i]
 
H communication 
知识点 
最小生成树
 
题目代码 
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n,m;
struct node{
	ll val;
	ll id;
	bool operator<(const node &rh)const{
		return val 
结语 
遇事不决 可问春风
春风不语 即随本心
我若本心能定 怎会遇事不决 春风亦有春风愁 不劳春风为我忧。
自此春风盈满袖，只为一解平安愁