赛前冲刺套题day3

明天考试,很慌……

CSP-S2021加油!

[题目1]绿洲

这题真·卡常数到极致......

其实这题也没有那么难,就是做K遍最短路

因为边权为1,所以最短路算法应选择bfs()(没想到吧)

另几个最短路算法(dijkstra(未知),dijkstra堆优化(80分),spfa(90分)……)均不能满分(开O3+快读卡常数除外)

所以我选择了卡常数……


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,m,k;
int city[100005],final_dist[100005];
int h[100005],e[200005],ne[200005],idx;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(int S)//本人之前写的是dij堆优化,懒得把函数名改成spfa了
{
    int dist[100005],st[100005]={0};
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    queue<int> q;
    q.push(S);
    st[S] = true;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)final_dist[i]=max(final_dist[i],dist[i]);
}
int main()
{
    freopen("oasis.in","r",stdin);
    freopen("oasis.out","w",stdout);
    memset(h,-1,sizeof h);
    n=read();
    m=read();
    k=read();
    for(int i=1;i<=k;i++)city[i]=read();
    while(m--)
    {
        int a=read();
        int b=read();
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=k;i++)dijkstra(city[i]);
    for(int i=1;i<=n;i++)printf("%d ",final_dist[i]);
    return 0;
}

[题目2]数列

vector NB!!!
而且题解说要用并查集维护其实也是不用的


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int>A;
vector<int>pos[10005];
int main()
{
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        A.emplace_back(x);
    }
    A.emplace_back(0);
    int cnt=0,flag=1;
    for(int i=0;i<A.size();i++)
    {
        if(A[i])
        {
            pos[A[i]].emplace_back(i);
            flag=0;
        }
        else
        {
            if(!flag)cnt++;
            flag=1;
        }
    }
    int res=cnt;
    for(int i=0;i<=10000;i++)
    {
        for(auto item:pos[i])
        {
            if(A[item-1]&&A[item+1])cnt++;
            else if(!A[item-1]&&!A[item+1])cnt--;
            A[item]=0;
        }
        res=max(res,cnt);
    }
    printf("%d",res);
    return 0;
}

[题目3]遛狗

前置知识:P5490 【模板】扫描线


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long long LL;
int n,cnt=0;
LL x1,x2,y1,y2,X[N<<1];
struct scan
{
    LL l,r,h;
    int mark;
    bool operator < (const scan &P)const
    {
        return h<P.h;
    }
}line[N<<1];
struct tree
{
    int l,r,sum;
    LL len;
}tr[N<<2];
void build(int k,int l,int r)
{
    tr[k]={l,r,0,0};
    if(l==r)return;
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void pushup(int x)
{
    int l=tr[x].l;
    int r=tr[x].r;
    if(tr[x].sum)tr[x].len=X[r+1]-X[l];
    else tr[x].len=tr[x<<1].len+tr[x<<1|1].len;

}
void modify(int x,LL L,LL R,int c)
{
    int l=tr[x].l;
    int r=tr[x].r;
    if(X[r+1]<=L||R<=X[l])return;
    if(L<=X[l]&&X[r+1]<=R)
    {
        tr[x].sum+=c;
        pushup(x);
        return;
    }
    modify(x<<1,L,R,c);
    modify(x<<1|1,L,R,c);
    pushup(x);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        X[2*i-1]=x1;
        X[2*i]=x2;
        line[2*i-1]={x1,x2,y1,1};
        line[2*i]={x1,x2,y2,-1};
    }
    n<<=1;
    sort(line+1,line+n+1);
    sort(X+1,X+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
    build(1,1,tot-1);
    LL ans=0;
    for(int i=1;i<n;i++)
    {
        modify(1,line[i].l,line[i].r,line[i].mark);
        ans+=tr[1].len*(line[i+1].h-line[i].h);
    }
    printf("%lld",ans);
    return 0;
}

然后就没有然后了……

[题目4]食材运输

说是都是暴力,但我要二分[doge]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,M=15,INF=1<<29;
typedef long long LL;
typedef pair<int,int>PII;
int n,m,k,idx,h[N],d[N][M],g[N][M];
struct Edge
{
    int e,ne,w;
}edge[N*2];
void add(int u,int v,int w)
{
    edge[++idx]={v,h[u],w};
    h[u]=idx;
}
PII dfs(int u,int father,int op)
{
    PII res={0,-1};
    if(g[u][op])res.second=0;
    for(int i=h[u];i;i=edge[i].ne)
    {
        int to=edge[i].e;
        int w=edge[i].w;
        if(to==father)continue;
        auto t=dfs(to,u,op);
        if(t.second!=-1)
        {
            res.first+=t.first+(w*2);
            res.second=max(res.second,t.second+w);
        }
    }
    return res;
}
int state[N],f[1<<M];
bool check(int mid)
{
    memset(state,0,sizeof state);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            if(d[i][j]<=mid)state[i]|=(1<<j);
        }
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(1<<k);j++)f[j|state[i]]=min(f[j|state[i]],f[j]+1);
    }
    return f[(1<<k)-1]<=m;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)scanf("%d",&g[i][j]);
    }
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            auto t=dfs(i,-1,j);
            if(t.second!=-1)d[i][j]=t.first-t.second;
        }
    }
    int l=0,r=INF;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",r);
    return 0;
}

最后

CSP-S 2021 加油!

CSP-S 2021 加油!

CSP-S 2021 加油!

赛前冲刺套题day2(还剩下1天练习时间)

我没了,我没了,我真的没了

又是《简单》的一套题。

[题目一]成绩

枚举,但细节非常的多。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,dot;
char s[200010];
void Cout(int start,int end)
{
    for(int i=start;i<=end;i++)printf("%c",s[i]);
    exit(0);
}
void solve(int i)
{
    while(i>=0&&s[i]=='9')s[i--]='0';
    if(i==-1)
    {
        printf("1");
        Cout(0,dot-1);
        return;
    }
    s[i]++;
    Cout(0,dot-1);
}
int main()
{
    freopen("grade.in","r",stdin);
    freopen("grade.out","w",stdout);
    scanf("%d%d%s",&n,&m,s);
    if(!m)Cout(0,n-1);
    for(int i=0;i<n;i++)
    {
        if(s[i]=='.')
        {
            dot=i;
            break;
        }
    }
    for(int i=dot+1;i<n;i++)
    {
        if(s[i]>='5')
        {
            if(i==dot+1)solve(dot-1);
            else
            {
                int j=i-1;
                s[j]++;
                int t=1;
                while(t+1<=m&&j!=dot&&s[j]=='5')
                {
                    t++;
                    s[--j]++;
                }
                if(j==dot)solve(dot-1);
                Cout(0,j);
            }
        }
    }
    Cout(0,n-1);
    return 0;
}

[第二题]数三角形

数学题,求组合数,用总的方案数-三个点构成直线平行于横轴-三个点构成直线平行于竖轴-三个点构成直线的其他情况


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long ans=0;
long long C(long long x)
{
    return x*(x-1)*(x-2)/6;
}
int main()
{
    freopen("tri.in","r",stdin);
    freopen("tri.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    n++;
    m++;
    ans=C(n*m)-m*C(n)-n*C(m);
    for(long long i=1;i<n;i++)
    {
        for(long long j=1;j<m;j++)ans-=2*(n-i)*(m-j)*(__gcd(i,j)-1);
    }
    printf("%lld",ans);
    return 0;
}

[第三题]苹果

万万没有想到,这题竟是一个测试运气的题目

每次从a[]中随机出两个不同下标的数,对他们求gcd(),并把他们的求得gcd的结果分解因数并存到一个数组里(这个步骤多重复几次,多了正确性大,但是不要太大,会导致时间超限),后面就是从大的->小的因数去试一试a[]中的数是否有半数可以整除这个因数,找到就输出并break。

另:二分只有5~10分(有可能是本人二分出错了......)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
const long long N=200005;
long long n;
long long a[N];
vector<long long>divers;
void F(long long x)
{
    for(long long i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            divers.push_back(i);
            if(i!=x/i)divers.push_back(x/i);
        }
    }
}
int main()
{
    freopen("apple.in","r",stdin);
    freopen("apple.out","w",stdout);
    srand(time(0));
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)scanf("%lld",&a[i]);
    long long T=39;
    while(T--)
    {
        long long xb1=rand()%n+1;
        long long xb2=rand()%n+1;
        while(xb1==xb2)
        {
            xb1=rand()%n+1;
            xb2=rand()%n+1;
        }
        F(__gcd(a[xb1],a[xb2]));
    }
    sort(divers.begin(),divers.end());
    divers.erase(unique(divers.begin(),divers.end()),divers.end());
    for(long long i=divers.size()-1;i>=0;i--)
    {
        long long ans=0;
        for(long long j=1;j<=n;j++)
        {
            if(a[j]%divers[i]==0)ans++;
        }
        if(ans*2>=n)
        {
            printf("%lld",divers[i]);
            return 0;
        }
    }
    printf("1");
    return 0;
}

永远不会的第四题........

CSP-S考前冲刺DAY1

今天第一天集训,虽然难度不算难,但出现了亿些些不会写的东西。

[题目1]线段树

正如这道题的名字一样,正解就是线段树,只不过还要维护乘法(暴力没有分!!),线段树不熟,挂了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=10007;
ll n,m;
ll a[100010],Jsum[500010],Csum[500010];
void build(ll k,ll l,ll r)//建树
{
    if(l==r)
    {
        Jsum[k]=Csum[k]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    Jsum[k]=(Jsum[k<<1]+Jsum[k<<1|1])%mod;
    Csum[k]=(Csum[k<<1]*Csum[k<<1|1])%mod;
}
void change(ll k,ll l,ll r,ll x,ll v)//更改数值
{
    if(l==r)
    {
        Jsum[k]=Csum[k]=v;
        return;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)change(k<<1,l,mid,x,v);
    else change(k<<1|1,mid+1,r,x,v);
    Jsum[k]=(Jsum[k<<1]+Jsum[k<<1|1])%mod;
    Csum[k]=(Csum[k<<1]*Csum[k<<1|1])%mod;
}
ll queryC(ll k,ll l,ll r,ll x,ll y)//查询乘法
{
    if(r<x||l>y)return 1;
    if(x<=l&&r<=y)return Csum[k];
    ll mid=(l+r)>>1;
    ll res1,res2;
    res1=queryC(k<<1,l,mid,x,y);
    res2=queryC(k<<1|1,mid+1,r,x,y);
    return (res1*res2)%mod;
}
ll queryJ(ll k,ll l,ll r,ll x,ll y)//查询加法
{
    if(r<x||l>y)return 0;
    if(x<=l&&r<=y)return Jsum[k];
    ll mid=(l+r)>>1;
    ll res1,res2;
    res1=queryJ(k<<1,l,mid,x,y);
    res2=queryJ(k<<1|1,mid+1,r,x,y);
    return (res1+res2)%mod;
}
// 初始化部分

线段树真的特别长,而且特别容易写挂,在OJ上交了好几次0分的代码………………(还有一本通的线段树的模板题是不用写build()函数的……,于是把build()打挂提交了好几次)

这个是不带懒标记的,带懒标记的题目有这个

附代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,w[N];
struct node
{
    int l,r;
    LL sum,add;
}tree[N*4];
void pushup(int u)
{
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void pushdown(int u)
{
    auto &root=tree[u],&left=tree[u<<1],&right=tree[u<<1|1];
    if(root.add)
    {
        left.add+=root.add;
        left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add;
        right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}
void build(int u,int l,int r)
{
    if(l==r)tree[u]={l,r,w[r],0};
    else
    {
        tree[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int d)
{
    if(tree[u].l>=l&&tree[u].r<=r)
    {
        tree[u].sum+=(LL)(tree[u].r-tree[u].l+1)*d;
        tree[u].add+=d;
    }
    else
    {
        pushdown(u);
        int mid=tree[u].l+tree[u].r>>1;
        if(l<=mid)modify(u<<1,l,r,d);
        if(r>mid)modify(u<<1|1,l,r,d);
        pushup(u);
    }
}
LL query(int u,int l,int r)
{
    if(tree[u].l>=l&&tree[u].r<=r)return tree[u].sum;
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    LL sum=0;
    if(l<=mid)sum+=query(u<<1,l,r);
    if(r>mid)sum+=query(u<<1|1,l,r);
    return sum;
}
//一些初始化......

不会的第二题……

[第三题]礼物

DP......


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005,mod=1e7+7;
int f[N][N],c[N];
int n,m,sum;
int main()
{
    freopen("gift.in","r",stdin);
    freopen("gift.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        sum+=c[i];
    }
    if(sum<=m)//特判所有物品价格的和不大于m的情况,此时只有一种方案
    {
        printf("1");
        return 0;
    }
    sort(c+1,c+n+1);//设f[i][j]表示考虑前i件物品,剩余j元的方案数
    f[n][c[n]]=1;
    f[n][0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=c[i])f[i][j]=(f[i][j]+f[i+1][j-c[i]])%mod;
            f[i][j]=(f[i][j]+f[i+1][j])%mod;
        }
    }
    int rest=0,ans=0;
    for(int k=1;k<=n;k++)
    {
        rest=m;
        for(int i=1;i<k;i++)rest-=c[i];
        if(rest<0)break;
        for(int i=max(rest-c[k]+1,0);i<=rest;i++)ans=(ans+f[k+1][i])%mod;
    }
    printf("%d",ans);
    return 0;
}

[第四题]宋伊雪的惩罚

长乐OJ原题,枚举中心点,二分最大的边长,判断相等时用二维HASH,真是不错的一道题目呢


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int n,m;
typedef unsigned long long ULL;
const ULL base1=87,base2=31;//模数随便取(要质数)
ULL a[N][N],b[N][N],c[N][N],Hasha[N][N],Hashb[N][N],Hashc[N][N],fact1[N],fact2[N],ans;
bool check(int len,int x,int y)
{
    if(x>n||y>m||x<len||y<len)return 0;
    ULL HASHa=0,HASHb=0,HASHc=0;
    HASHa=Hasha[x][y]-Hasha[x-len][y]*fact2[len]-Hasha[x][y-len]*fact1[len]+Hasha[x-len][y-len]*fact1[len]*fact2[len];
    int t=y;
    y=m-(y-len);
    HASHb=Hashb[x][y]-Hashb[x-len][y]*fact2[len]-Hashb[x][y-len]*fact1[len]+Hashb[x-len][y-len]*fact1[len]*fact2[len];
    y=t;
    x=n-(x-len);
    HASHc=Hashc[x][y]-Hashc[x-len][y]*fact2[len]-Hashc[x][y-len]*fact1[len]+Hashc[x-len][y-len]*fact1[len]*fact2[len];
    return HASHa==HASHb&&HASHb==HASHc;
}
ULL B(int i,int j,int x=0)
{
    int l=0,r=min(i,j)+f,Ans=x;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid*2-x,i+mid,j+mid))
        {
            l=mid+1;
            Ans=mid*2-x;
        }
        else r=mid-1;
    }
    return (Ans+1)/2;
}
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    fact1[0]=fact2[0]=1ULL;
    for(int i=1;i<=n;i++)fact1[i]=fact1[i-1]*base1;
    for(int i=1;i<=m;i++)fact2[i]=fact2[i-1]*base2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][m-j+1]=c[n-i+1][j]=a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            Hasha[i][j]+=Hasha[i][j-1]*base1+a[i][j];
            Hashb[i][j]+=Hashb[i][j-1]*base1+b[i][j];
            Hashc[i][j]+=Hashc[i][j-1]*base1+c[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            Hasha[i][j]+=Hasha[i-1][j]*base2;
            Hashb[i][j]+=Hashb[i-1][j]*base2;
            Hashc[i][j]+=Hashc[i-1][j]*base2;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)ans+=B(i,j,1)+B(i,j);
    }
    printf("%llu",ans);
    return 0;
}

一涉及提高组字数就多到爆炸......

国庆集训DAY3

今天的题目又加强了

石子合并

第一题,一道分析题,看懂了就简单。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
for(ll i=1; i<=n; i++) {
            a[i] = read();
           
            if(a[i]>0)
            {
                zs++;
                zx = min(zx,a[i]);
                zz += a[i];
            }
            if(a[i]<0)
            {
                a[i] = abs(a[i]);
                fs++;
                fd = min(fd,a[i]);
                fz += a[i];
                a[i] -= 2*a[i];
            }
            if(a[i]==0)zl = 1;
        }
        if(n==1)
        {
            cout<<a[1]<<endl;
            continue;
        }
        else if((zs&&fs)||zl == 1)
            ans = zz + fz;
        else if(zs)
            ans = zz-2*zx;
        else if(fs)
            ans = fz-2*fd;

铺地毯

第二题。看一眼数据范围:1n3×105,1P,Q109,1T5

1n3×105,1P,Q109,1T5

哦这不是我能打出来的。

优美的旋律

第三题,判断重复字符子串个数,按照题目要求去算。

是个能看懂的题目。

我用了一手string.find()

这很不错。

直接暴力拿下60分。

 

第四题不讲。

 

顺带提一句,今天的数据坑人

,每个测试点多个数据

一个不小心就没了

国庆集训DAY2

谈谈今天的题目。

第一题简单题,两个单元最短路然后选择一个最短组合。

第二题打爆力60分,(正解比较难思考)

第三、第四题,我根本看不懂……

综上,我也不知道我怎么弄的样例分。

中转站

算一个模板题。按上面的说法做就完了。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct node{
    ll u,v,w;
    ll next;
}zz[2*M];
void jy(ll u,ll v,ll w)
{
    pos++;
    zz[pos].u = u;
    zz[pos].v = v;
    zz[pos].w = w;
    zz[pos].next = head[zz[pos].u];
    head[zz[pos].u] = pos;
    return;
}

priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
ll dis[N];
ll vis[N];
void Dij(ll from)
{
    ll u;
    for(int i=1;i<=n;i++)
    {
        dis[i]=1e13;vis[i] = 0;
    }
       
    dis[from] = 0;
    q.push(make_pair(0,from));
    while(!q.empty())
    {
        u = q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(ll i=head[u];i;i=zz[i].next)
        {
            if(dis[zz[i].v]>dis[zz[i].u]+zz[i].w)
            {
                dis[zz[i].v] = dis[zz[i].u]+zz[i].w;
                q.push(make_pair(dis[zz[i].v],zz[i].v));
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        if(from==s)c[r[i]] = dis[r[i]];
        else ans = min(ans,c[r[i]]+dis[r[i]]);
    }
    return;
}

粒子自撞机

一个数学题。

用扩展欧几里得来求正解。

这是欧几里得模板

正解我也不会。

 

 

国庆集训DAY 1

今天的题目很有意思

水题但是看不出来。

难题又难到不会。

这边说前两题

破门而入(broken)

分析一下题目,其实这只输入两个数的,一般都是有规律的,因为数据范围比较大就有这个考虑。(就是考试我也没看出来)

分析多一个点的情况下,会不会多一个环,就可以弄出递推式。


1
2
3
4
5
for(int j=1;j<=k;j++)f[1][j] = 1;
    for(int i=2;i<=n;i++)f[i][1] = f[i-1][1]*(i-1)%N;
    for(int i=2;i<=n;i++)
        for(int j=2;j<=k;j++)
            f[i][j] = (f[i-1][j]*(i-1)+f[i-1][j-1])%N;

 

翻转游戏(turn)

我的考试时思路很简单,就是暴力(翻转,哈希)。

谁知道到这玩意也能有规律。

先求出所有的变法个数(只翻转一个的不算,但是只翻转一个的也就一种答案情况)

然后减去所有字母的(个数*个数减一)/2,就是减去所有翻转后无用的情况。

再然后

……

就没有然后了。


1
2
3
    ans = (n-1)*n/2+1;
    for(int i=97;i<=122;i++)
        ans -= a[i]*(a[i]-1)/2;