1004-Link with Equilateral Triangle

来源: 杭电杯超级联赛4 算法: 图形规律题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1047&pid=1004 补完: Yes 完成时间: August 12, 2022

题目链接

题意简述

给一个边长为n的大等边三角形，它被分割为边长为1的小等边三角形。

在小三角形顶点上填充数字，只能填0，1，2；并且在大三角形的左边界不能填0，右边界不能填1，下边界不能填2。并且要求小三角形三个顶点上的数字不是3的倍数。

问能否找到满足条件的方案。

题目分析

开场就过这么多人，样例还是不满足，模拟了两个三角形找不到方案，那这不得交一发输出No吗？

~~过了，本题解到此结束。~~

开玩笑的，不严格证明还是要放一点的。

首先，由于小三角形顶点和要满足不是3的倍数，我们先枚举0，1，2的组合可能，选取合法组合：

也就是一种数字1个，另一个种数字2个的组合是可行的。

接着，由于各个边均有限制，那么大三角形的节点必然是固定的。如图。

那么我们从左下顶点1开始填数字。由于两边一个不能填0，一个不能填2，把1作为那个只有一个的数字是不可行的，只能在其中一边填上1，另一边是对应的没被限制的0或者2，这里以1，0选择为例，由于图形对称，另一种选择与本选择同理。则有：

这样向右又有一个小三角形两顶点已知（1和0）可以填入0或1。

并且，由于大三角形左边界不能填0，如果这个三角形也填1，边界只能是2。

也就是有两种情况：

①边界填1，小三角形填0：

②边界填2，小三角形填1：

对于①，左下平行左边界的小三角形边已知两个点都是0，下边界不能填2，那么这个三角形贴下边界的点只能是1。而再下一个三角形两个顶点是1和0，第三个顶点就只能是1或者0。这个三角形如果是1，1，第三个顶点只能是0，如果是1，0，第三个顶点只能是1或者0。

这使得整串顶点都是1或者0。而且每一个看似自由的1/0选择都定死了另一个点的选择：比如上图中第一个0/1，选择0则固定了上方顶点必然为1，选择1则固定了下方顶点必然为0.

到右边界的时候，由于右下顶点是0，右边界不能为1，所以只有两种情况：右边界填2，下边界填0；右边界填0，下边界填1。

而这个选择看着是自由选择的，实际上会锁定上方或者下方的数字。而另一侧已经被角落的1固定了一部分，所以下侧的01选择会根据最下层三角形的数量而固定。

而右侧要么会一直是0，要么中途借着边界的一个0和左边一个节点0把侧边修改成2.左侧同理，要么一直是1，要么需要借着右边也来一个1，把下一个节点修改成2.

到了最上面的节点，冲突就会出现：如果右侧的数字是2，左侧只能是1.

左右如果都没在这里发生变化，那么中间的数字一定是0：

1，2，0同时出现，情况非法。

如果1下一个位置是2，那么中间只能是1。又由于底下的数字限制了中间上方会出现的都是0和1（如果让2出现相当于是从2节点之类的开始的另外的对称情况），当中间是1，那么要么在右侧0和2置换的时候出现0，1，2的三角形，要么在两侧都是2的情况下出现1，1，1的三角形。

具体的情况可以手动模拟一下，总之，三个节点三条边之间的限制让不合法组合的冲突无法避免，每一步暂时的维稳只能把僵局往一个方向推动，必然在一个小三角形的位置产生限制冲突且无法解决。

不完整代码

1	cout<<"No";

1006-BIT Subway

来源: 杭电杯超级联赛4 算法: 模拟, 语法题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1047&pid=1006 补完: Yes 完成时间: July 31, 2022

题解

Dlee的理解是超过100元的钱打八折, 超过200元的钱打五折

也就是超过100元的花费0.8元值1元, 在100~200区间就是100元值125元.

真实运行是当已购票价超过100元后再买的票才打八折, 已购票价超过200元后再买的票才打五折.

代码

#include<bits/stdc++.h>
using namespace std;
int T,n;
void solve(){
    double DLee_ans=0,True_ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        double ticket;
        scanf("%lf",&ticket);
        DLee_ans+=ticket;
        if(True_ans>=200){
            True_ans+=ticket*0.5;
        }
        else if(True_ans>=100){
            True_ans+=ticket*0.8;
        }
        else {
            True_ans+=ticket;
        }
    }
    if(DLee_ans>=225)DLee_ans = (DLee_ans-225)*0.5+200;
    else if(DLee_ans>=100)DLee_ans = (DLee_ans-100)*0.8+100;
    printf("%.3lf %.3lf\n",DLee_ans,True_ans);
}
int main(){
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

1007 Climb Stairs

来源: 杭电杯超级联赛4 算法: 区间和维护, 贪心题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1047&pid=1007 补完: Yes 完成时间: August 1, 2022

题意简述

有n级楼梯，每个楼梯上有一个怪物，每个怪物有一个生命值\(a_i\)。（为与攻击力区分，后文用\(hp_i\)表示）

主角一开始在地面，可以当作第0级楼梯。主角有初始攻击力\(a_0\)。

每次主角可以向上跳跃\(k\)级以内的楼梯，即第一步可以到达1~k层；或者向下走一级楼梯。走过的楼梯不可以再走。

他只能去打得过的怪物在的楼梯。当怪物的生命值不超过他的攻击力他就打得过。打完怪物他的攻击力会加上怪物的生命值。

问是否可以打完所有怪物。

题目分析

////

首先，由于走楼梯的方法是向上可以跳，但向下只能一步一步走，那么要打完所有怪物，意味着每次从i级楼梯向上跳跃之后必须一步一步走回来，直到把\(i+1\)级上的怪物也打完，否则之后没有机会再回到被跳过的这一段了。

也就是说，在跳跃能力\(k\)之内，只有跳跃后能逆着把这整段怪物依次打败的楼梯才能选择。如果没有选择了，就无法行动了。

////

那么，如果在跳跃范围内有多个点可以选择，选谁呢？

我们思考一下跳跃后扫完整段的怪物后是什么情况：假设我们从i级开始跳，跳到\(j\)，扫完之后我们人在i+1级，由于达到过的地方不能再去，下一次跳跃选择范围是\([j+1，i+1+k]\)。

可以发现，下次的选择范围的最高点是固定的，最低点受到这次跳跃的影响。这次跳跃的越远，j越大，下次的选择范围就越小。

所以既然有多个选择，我们应该选择距离较近的那个，也就是让j尽可能小。因为怪物的血量分布是没有规律的，选择范围越小，就越可能打不过范围内的怪物。

也许你会说，向下扩展的范围是较高点那个选择本来就能打得过的，该吃的血条不都吃干净了吗？

但是，留出这个扩展范围做选择，不仅是让这次跳跃变得可能继续，也让最后的落点在更高的位置，也就是完成一次跳跃之后，新的i出现了，这让再下一次的跳跃范围的最高点，新的\(i_a+1+k\)，比直接跳到更高层的，和跳到更低层一样的，旧的\(i_b+1+k\)，更高得多，获取了更多可能存在的怪物跳板——毕竟打一个小怪也能让自己的攻击力提升。

////

最后，怎么判断这个位置能不能跳，也就是能不能顺着这个位置把中间的怪物打个干净呢？

对于一个位置在\(l\)的怪物，跳到\(r\)点回来攻击它的时候的攻击力是：

跳跃前的攻击力\(a\)+从\(r\)点杀到\(l+1\)点多获得的攻击力\(\sum_{i=l+1}^{r} hp_i\)

这个数值大于当前怪物的\(hp_l\)即可。

那么最先被想到的可能是前缀和，它可以方便地查找这样的区间和。但这意味着每次尝试跳跃的时候，都要在跳跃区间进行一次区间和的查询，总体的效率会接近\(O（n^2)\) ，这个时间复杂度是不被允许的。~~（AC之后交了一发试试果然TLE了）~~

////

我们换个思路考虑。先从最小规模的问题开始：如果是判断落点j的前一个位置能不能下楼击杀呢？那么可行条件就是\(hp_{j-1} ≤ a+hp_j\)

对于当前攻击力\(a\)来说，就是\(a≥hp_{j-1}-hp_j\)

再往下一个，即为\(hp_{j-2}≤a+hp_j+hp_{j-1}\)

化为\(a≥hp_{j-2}-hp_j-hp_{j-1}\)

以此类推，对每个\(l\)来说，从跃点\(j\)回头击杀i位置怪物的条件就是：

\(a>=hp_l-\sum_{i=l+1}^jhp_i\)

~~这不就刚那式子换个位置吗~~

确实，确实。

但其实思路里没化简的累减部分正是替代前缀和的关键。

并且，归纳到整段对a的影响，也就是a要≥所有跳跃范围中累计出来的最大值。

这意味着我们顺着楼梯上去的方向跑，就可以一边累减一边维护这个\(a\)要对比的值，记作\(cmp\)。当前攻击\(a\)大于这个楼梯上怪物的\(hp\)，且大于这个比较值，就说明\(a\)可以击败这个楼梯上的怪物并把越过的怪物回去一锅端了。如果打不了，那可以把这个楼梯上的小玩意也抓去累减，指望后面的怪物的血条贡献的攻击力可以补救它。

我们使用一个变量\(lever\)记录我们已经干碎了的怪物的范围，每次合法的跃点就是这个范围的最新上界。再使用一个变量\(stp\)记录当前跳跃前踩的楼梯，每次跳跃由于要回头收割，跳跃前的楼梯一定只能是当前的再走上去一级。\(stp+k\)就是能达到的最远楼梯。超过这个范围还找不到能跳跃的点，怪物猎杀就宣告失败了。

完整代码

#include<iostream>
#include<stdio.h>
using namespace std;
int hp[100010];
long long s[100010];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,a0,k;
		cin>>n>>a0>>k;
		long long a=a0;
		long long cmp=0;
		for(int i=1;i<=n;i++){
			cin>>hp[i];
			s[i]=s[i-1]+hp[i];
		}
		int stp=0;//当前位置
		int lever=0;//收割范围 
		for(int i=1;i<=n&&i-stp<=k;i++){
			if(a>=hp[i]&&a>=cmp){
				a+=s[i]-s[lever];
				lever=i;
				stp++;//回头收割方式 步伐只能前进1
				cmp=0; 
			}
			else{
				cmp=max((long long) (hp[i]-hp[i+1]),(long long)(cmp-hp[i+1]));
			} 
		}
		if(lever==n)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

1011-Link is as bear

来源: 杭电杯超级联赛4 算法: 数论, 线性基题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1047&pid=1011 补完: Yes 完成时间: July 28, 2022

题解

题目给操作: 任取子序列赋值为全体异或和. 要求全体最大异或和.

等价于给\(n\)个数, 求其中任选某些数的最大异或和.

用线性基解决.

代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int T,n;
ll a,ans;
vector<ll> Base;
void insert(ll x) {
    for(auto b : Base)
        x = min(x,b^x);
    for(auto &b : Base)
        b = min(b,b^x);
    if(x)
        Base.push_back(x);
}
void solve(){
    ans = 0;
    Base.clear();
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        insert(a);
    }
    for(auto x : Base){
        ans ^= x;
    }
    cout<<ans<<endl;
}
int main(){
    cin>>T;
    while(T--)solve();
    return 0;
}

Shelter

2022杭电杯超级联赛04

1004-Link with Equilateral Triangle

题意简述

题目分析

不完整代码

1006-BIT Subway

题解

代码

1007 Climb Stairs

题意简述

题目分析

完整代码

1011-Link is as bear

题解

代码