杭电杯第四场

个人题解，欢迎指正

P1004

思路：

手推几种情况发现全是 no

Code:

#include<bits/stdc++.h>
#define ll long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}




void ClearDewy(){
    int n=read();
    puts("No");


}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    ClearDewy();
    WA
}

P1006

思路：

一道模拟题，注意double的精度而不能直接==就可以了

#include<bits/stdc++.h>
#define ll long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

const double epx=1e-5;


void ClearDewy(){
    int n=read();
    double a=0,b=0;
    int x;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&x);
        if(b-100<-epx){
            b+=x;
        }else if(b-200<-epx){
            b+=0.8*x;
        }else b+=0.5*x;
        double t=x;

        if(a-100<-epx){
            double t1=min(100-a,t);
            a+=t1;t-=t1;
        }
        if(a-100>=-epx&&a-200<-epx){
            double t1=min((200-a)/0.8,t);
            a+=0.8*t1;t-=t1;
        }
        if(a-200>=-epx){
            a+=0.5*t;
        }
    }
    printf("%.3f %.3f\n",a,b);
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    ClearDewy();
    WA
}

P1007

思路：

维护一个栈，每次攻击把栈清空，且下次进栈的数量和本次清空的数量不能大于k

Code:

#include<bits/stdc++.h>
#define ll long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() { ll x = 0, z = 1; char c = getchar(); while (!isdigit(c)) { if (c == '-')z = -1; c = getchar(); }while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }return z * x; }
inline void writ(ll x) { if (x < 0) { putchar('-'); x = (~x) + 1; }if (x > 9)writ(x / 10); putchar(x - x / 10 * 10 + 48); }

int n, k;
ll sum;

void ClearDewy() {
    n = read(); sum = read(); k = read();
    vector<ll>a(n + 1);
    vector<ll>sta(k + 5); int cnt = 0, la = 0;
    bool ju = 1; ll mx = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        sta[++cnt] = a[i];
        mx = max(max(0LL, mx - sta[cnt]), sta[cnt - 1] - sta[cnt]);
        if (sum >= mx && sum >= sta[cnt]) {
            la = cnt;
            while (cnt)
            {
                sum += sta[cnt--];
            }
            mx = 0;
        }
        if (la + cnt > k) {
            ju = 0; for (int j = i + 1; j <= n; j++)a[j] = read();
            break;
        }
    }
    if (ju && !cnt) {
        puts("YES");
    }
    else puts("NO");

}



int main() {
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T = read(); while (T--)
        ClearDewy();
    WA
}

P1011

思路：

偶数个连续的进行两次操作就全为0，当一个数旁有0时，这个数可以扩展到任意位置。例如：

2 3 0 -> 2 3 3 -> 1 1 3 ->0 0 3 ->3 3 3

然后题目说有两个相同的数，我们可以把期中一个当做 “0”来用，不需要这个数时与另外一个数异或一下即可消去。

于是题目转化为从n个数中选任意个数使异或值最大

百度一下，线性基，CV了一个板子过了

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const int maxm=70;
int a[maxm];
int d[maxm],cnt;
void insertt(int x){
    for(int i=62;i>=0;i--){//从最高位开始(这里用的50)
        if(x>>i&1){//如果为1
            if(d[i]){
                x^=d[i];
            }else{
                d[i]=x;
                break;
            }
        }
    }
}

void ClearDewy(){
    int n;
    scanf("%lld",&n);
    memset(a,0,sizeof a);memset(d,0,sizeof d);cnt=0;
    for(int i=1,x;i<=n;i++){
        scanf("%lld",&x);
        insertt(x);
    }
    int ans=0;
    for(int i=62;i>=0;i--){
        if((ans^d[i])>ans)ans^=d[i];
    }
    printf("%lld\n",ans);
}

signed main(){
    int T;
    scanf("%lld",&T);
    while(T--)ClearDewy();
    return 0;
}