2022“杭电杯”中国大学生算法设计超级联赛（4）

Link with Equilateral Triangle

向等边三角形每个节点处填数字，规定每个位置不能填的数字，问是否有填数方案满足条件。

思路：多画几个，，真的没有，直接输出“No” 。

AC Code：

#include 
 
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod=1e9+7;
const int N=2e6+5;
int t,n;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n;
        std::cout<<"No"<<'\n';
    }
    return 0;
}

os：三个人画了好久hhhh

BIT Subway

买票消费满一百打八折，满二百打五折，但是这个人的计算方法与规定不同，他认为我们可以为了凑齐一百或者二百而买一张票的一部分价钱，这样另一部分就可以打折购买了，现在给出需要买的票的价格，计算两种方式下所需花的钱数。

思路：直接模拟计算即可。

AC Code：

#include 
 
const int N=1e5+5;
int t,n;
double a[N];
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lf",&a[i]);
        }
        double aa=0;
        bool flag1=false,flag2=false;
        for(int i=1;i<=n;i++){
            if(flag1&&!flag2) aa+=0.8*a[i];
            else if(flag2) aa+=0.5*a[i];
            else aa+=a[i];
            if(aa>=100){
                flag1=true;
            }
            if(aa>=200){
                flag2=true;
            }
        }
        double sum=0;
        int pos=-1;
        for(int i=1;i<=n;i++){
            if(sum+a[i]>100){
                pos=i;
                break;
            }
            sum+=a[i];
        }
        if(pos==-1){
            printf("%.3lf %.3lf\n",aa,aa);
            continue;
        }
        a[pos]=a[pos]-(100-sum);
        sum=0;
        int poss=-1;
        for(int i=pos;i<=n;i++){
            if(sum+a[i]>125){
                poss=i;
                break;
            }
            sum+=a[i];
        }
        if(poss==-1){
            printf("%.3lf %.3lf\n",sum*0.8+100,aa);
            continue;
        }
        a[poss]=a[poss]-(125-sum);
        sum=0;
        for(int i=poss;i<=n;i++){
            sum+=a[i];
        }
        printf("%.3lf %.3lf\n",sum*0.5+200,aa);
    }
    return 0;
}

os：注意保留小数的位数是确定的。

Climb Stairs

给出一列怪物，只有攻击力大于等于该怪物的生命力就可以打败它，然后它的生命力加到攻击力中。每次可以最多走k格或者退一格，不能走重复的格子，问是否有方案使得从头走到尾。

思路：每次找到能打的最近的位置，即如果碰到生命值较大的怪物，就向前看k个，找到现在能打且按顺序打下来之后能打一开始碰到的生命值较大的怪的位置，这个位置越靠前越好，直接贪心找即可，具体细节看代码。

大佬的代码！学习了

AC Code：

#include 
 
typedef long long ll;
const int N=1e5+5;
int t,n,k,x;
int a[N];
 
void work(){
	std::cin>>n>>x>>k;
	for(int i=1;i<=n;i++){
		std::cin>>a[i];
	}
	int cur=0,att=x,f=k;
	while(1){
		int max=0;
		bool flag=true;
		for(int i=cur+1;i<=n&&i-cur<=k;i++){
			//在k个范围内找合适的点
			max=std::max(max-a[i],a[i]);//找打i位置的怪需要的最小attack
			if(max<=att){
				//可以跳到前面的格子
				flag=false;
				for(int j=cur+1;j<=i;j++){
					att+=a[j];
				}
				k=f-(i-cur-1);
				cur=i;
				break;
			}
		}
		if(flag){
			std::cout<<"NO"<<'\n';
			return;
		}
		if(cur==n) break;
	}
	std::cout<<"YES"<<'\n';
}
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		work();
	}
	return 0;
}

 os：怎么说，这个题思路不算难，但是代码写起来需要思考一些细节，，所以这个题是队友写的我是菜比

Link is as bear

给定一个数组，每次操作可以使得区间[l,r]内的所有数变为这些数的异或和，问经过若干次操作后最大可以得到的数字是多少。

思路：线性基板子题，去学习呀

AC Code：

#include 
 
typedef long long ll;
int t,n;
ll a;
ll d[100];
 
void insert(ll x){
    for(int i=60;i>=0;i--){
        if(x&(1ll<
            if(d[i]) x^=d[i];
            else{
                d[i]=x;
                break;
            }
        }
    }
}
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		memset(d,0,sizeof(d));
		for(int i=1;i<=n;i++){
			std::cin>>a;
			insert(a);
		}
		ll ans=0;
    	for(int i=60;i>=0;i--){
    		if((ans^d[i])>ans) ans^=d[i];
    	}
    	std::cout<'\n';
	}
	return 0;
}

 Link with Bracket Sequence II

给出一个数字序列，某位置为0代表此处括号位置，若非0则代表括号，绝对值相同的代表一种括号，负数表示右括号，正数代表右括号， 问填满该序列的合法方案数。

思路：括号匹配，各种区间DP解题。。这里也不例外考虑区间DP，我们令f[l][r]表示l到r区间内是合法匹配且l和r处括号相互匹配的方案，g[l][r]表示区间[l,r]内括号匹配的方案数。这样f的转移是g的一种更特殊的情况。考虑区间段点，g[l][r]种找到一个分界线k，那么可以得出转移方程：g[l][r] += g[l][k - 1] * f[k][r]。这个堆叠方向是人为规定的，即f区间和g区间的前后关系不一定，这样是为了避免重复计数。

AC Code：

#include 
 
#define int long long
const int N=505;
const int mod=1e9+7;
int t,n,m;
int a[N],f[N][N],g[N][N];
 
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n>>m;
		for(int i=1;i<=n;i++){
			std::cin>>a[i];
		}
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		if(n&1){
			std::cout<<0<<'\n';
			continue;
		}
		for(int i=0;i<=n;i++){
			g[i+1][i]=1;
		}
		for(int len=2;len<=n;len+=2){
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1;
				if(a[l]>=0&&a[r]<=0){
					int tt=0;
					if(a[l]==0&&a[r]==0) tt=m;
					else if(a[l]==0||a[r]==0) tt=1;
					else if(a[l]+a[r]==0) tt=1;
					else tt=0;
					f[l][r]=g[l+1][r-1]*tt%mod;
				}
				for(int k=l;k<=r;k+=2){
					g[l][r]=(g[l][r]+g[l][k-1]*f[k][r]%mod)%mod;
				}
			}
		}
		std::cout<1][n]<<'\n';
	}
	return 0;
}

 Link with Running

求从1-n的最短路，路径上有两种权值w1，w2要求在w1最短的前提下w2最大， 并且w1，w2可能为0，但是保证一定有解。 

需要Dijkstra+tarjan+topsort，tarjan还没学，学了回来补。