国庆集训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;

 

P5304

啊,这题其实比较简单。

然后对于这个程序


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<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline long long read(){long long x;scanf("%lld",&x);return x;}
const long long N=15+5,M=75+5,inf=1e15;
long long T,n,m,k,in[N],ans;

long long fir[N],pre[M],nex[M],to[M],val[M],pos=0;
void add(long long x,long long y,long long v){
    to[++pos]=y;pre[pos]=x;nex[pos]=fir[x];fir[x]=pos;val[pos]=v;
}
void _delete(long long x){
    long long u=pre[x];
    fir[u]=nex[fir[u]];
    pre[x]=nex[x]=to[x]=val[x]=0;
}

void clear(){
    memset(in,0,sizeof(in));
    memset(fir,0,sizeof(fir));
    memset(nex,0,sizeof(nex));
    memset(to,0,sizeof(to));
    memset(val,0,sizeof(val));
    pos=0;ans=inf;n=m=k=0;
}

struct node{long long dian,far;}c;
bool operator <(node a,node b){return a.far>b.far;}
priority_queue<node> q;
long long dis[N],s,t;
long long dijk(){
    for(int i=s;i<=t;++i) dis[i]=inf;
    long long u=s;dis[s]=0;
    c.dian=s;c.far=0;q.push(c);
    while(!q.empty()){
        c=q.top();q.pop();u=c.dian;
        if(u==t) break;
        if(c.far>dis[c.dian])continue;
        for(long long i=fir[u];i;i=nex[i]){
            long long v=to[i];
            if(dis[u]+val[i]>=dis[v]) continue;
            dis[v]=dis[u]+val[i];
            c.dian=to[i];c.far=dis[v];
            q.push(c);
        }
    }
    while(!q.empty()) q.pop();
    return dis[t];
}

int main(){
    freopen("in.txt","r",stdin);
    T=read();
    while(T--){
        clear();
        n=read(),m=read(),k=read();
        for(long long i=1;i<=m;++i){
            long long x=read(),y=read(),z=read();
            if(x!=y) add(x,y,z);
        }
        for(long long i=1;i<=k;++i)
          in[read()]=1;
        s=0,t=n+1;
        for(long long l=1;l<=n;l<<=1){
            for(long long u=1;u<=n;++u)
              if(in[u])
                u&l?add(s,u,0):add(u,t,0);
            ans=min(ans,dijk());
            for(long long i=m+1;i<=pos;++i)
              _delete(i);
            pos=m;
        }
        for(long long l=1;l<=n;l<<=1){
            for(long long u=1;u<=n;++u)
              if(in[u])
                u&l?add(u,t,0):add(s,u,0);
            ans=min(ans,dijk());
            for(long long i=m+1;i<=pos;++i)
              _delete(i);
            pos=m;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

它是错的

跑得时候会跑出dis[t]=0来

原因是实际的边数没有m条,在pos-m编号的临时边没有被删去

无聊之举——打题

Intersecting Lines

题目大意

给定两组四个点,判断所确定的两条直线位置关系(平行,相交or重合)

自己花10分钟打了个代码,样例过了,但a不过去

为什么


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
#include<iostream>
#include<cstdio>
using namespace std;

int n;
int x1,y1,x2,y2,x3,y3,x4,y4;//四个点的座标
double k1,b1,k2,b2,x,y;//k表示斜率,b表示常数,x,y表示目标点

int main()
{
    scanf("%d",&n);
    printf("INTERSECTING LINES OUTPUT\n");
    for(int i=1; i<=n; i++)
    {
        scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        if(x1!=x2&&x3!=x4)//判断是否垂直与x轴
        {
            k1=(y1-y2)*1.0/(x1-x2);
            k2=(y3-y4)*1.0/(x3-x4);
                        //求斜率
            b1=y1-k1*x1;
            b2=y3-k2*x3;
                        //求函数常数
            if(k1==k2)
            {
                if(b1!=b2)
                    printf("NONE\n");
                else printf("LINE\n");
            }
            else
            {
                x=(b2-b1)/(k1-k2);
                y=x*k1+b1;
                                //求目标点座标
                printf("POINT %.2lf %.2lf\n",x,y);
            }
        }
        else
        {
            if(x1==x2)
            {
                if(x3==x4)
                {
                    if(x3!=x1)
                        printf("NONE\n");
                    else
                        printf("LINE\n");
                }
                else
                {
                    k2=(y3-y4)*1.0/(x3-x4);
                    b2=y3-k2*x3;
                    x=x1;
                    y=x1*k2+b2;
                    printf("POINT %.2lf %.2lf\n",x,y);
                }
            }
            //分别特判
            if(x3==x4)
            {
                if(x1==x2)
                {
                    if(x3!=x1)
                        printf("NONE\n");
                    else
                        printf("LINE\n");
                }
                else
                {
                    k1=(y1-y2)*1.0/(x1-x2);
                    b1=y1-k1*x1;
                    x=x3;
                    y=x3*k1+b1;
                    printf("POINT %.2lf %.2lf\n",x,y);
                }
            }
        }
    }
    printf("END OF OUTPUT");
    return 0;
}

我还能在想想

Bye

rand()的一次mle

P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题,我们参考第一篇满是注释的题解,写出一个很像的代码

众所周知,Windows系统下rand()取值为0-32000左右,dat为一个差不多的正数


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
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5,INF=1e9;
int n;

class treap{
    public:
        int val[N],dat[N],ch[N][2],tot,size[N],cnt[N],root;
        int _new(int x){
            val[++tot]=x;
            dat[tot]+=rand()+N;
            size[tot]=1;
            cnt[tot]=1;
            return tot;
        }
        void pushup(int u){
            size[u]=size[ch[u][0]]+size[ch[u][1]]+cnt[u];
        }
        void built(){
            root=_new(-INF);
        }
        void rotate(int &u,int d){
            int v=ch[u][d^1];
            ch[u][d^1]=ch[v][d];
            ch[v][d]=u;
            u=v;
            pushup(ch[u][d]),pushup(u);
        }
        void insert(int &u,int x){
            if(!u)
              {u=_new(x);return ;}
            if(x==val[u])
              cnt[u]++;
            else{
                int d=x<val[u]?0:1;
                insert(ch[u][d],x);
                if(dat[u]<dat[ch[u][d]]) rotate(u,d^1);
            }
            pushup(u);
        }
        void remove(int &u,int x){
            if(!u) return ;
            if(x==val[u]){
                if(cnt[u]>1){cnt[u]--;pushup(u);return ;}
                if(ch[u][0]||ch[u][1]){
                    int d=dat[ch[u][0]]>dat[ch[u][1]]?0:1;
                    rotate(u,d^1);
                    remove(u,x);
                }
                else
                  u=0;
                return ;
            }
            x<val[u]? remove(ch[u][0],x):remove(ch[u][1],x);
            pushup(u);
        }
        int get_rank(int u,int x){
            if(!u) return 0;
            if(x>val[u])  return size[ch[u][0]]+cnt[u]+get_rank(ch[u][1],x);
            if(x==val[u]) return size[ch[u][0]];
            if(x<val[u])  return get_rank(ch[u][0],x);
            return 0;
        }
        int get_val(int u,int x){
            if(size[ch[u][0]]>=x) return get_val(ch[u][0],x);
            if(size[ch[u][0]]+cnt[u]>=x) return val[u];
            return get_val(ch[u][1],x-size[ch[u][0]]-cnt[u]);
        }
        int get_pre(int u,int x){
            if(!u) return -INF;
            if(val[u]<x) return max(val[u],get_pre(ch[u][1],x));
            else return get_pre(ch[u][0],x);
        }
        int get_nex(int u,int x){
            if(!u) return INF;
            if(val[u]>x) return min(val[u],get_nex(ch[u][0],x));
            else return get_nex(ch[u][1],x);
        }
}t;

int main(){
    t.built();
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) t.insert(t.root,x);
        if(opt==2) t.remove(t.root,x);
        if(opt==3) printf("%d\n",t.get_rank(t.root,x));
        if(opt==4) printf("%d\n",t.get_val(t.root,x+1));
        if(opt==5) printf("%d\n",t.get_pre(t.root,x));
        if(opt==6) printf("%d\n",t.get_nex(t.root,x));
    }
    return 0;
}

然后就会MLE

真是让人好奇啊,并且ll就AC了,反复测试后,发现rand出问题

随机函数 - OI Wiki (oi-wiki.org)于是乎,Linux的rand()直接开到int上线

所以

rand()要考虑ll取模!

rand()要考虑ll取模!

rand()要考虑ll取模!

鸣谢陈涣焕学长的指导

ybt周赛9.12

2021.9.12

冲刺 NOIP2021 模拟赛 B 组 Day2

1.long long 相乘取模(归宿乘)

①(x)10→(x)2,(y)10→(y)2

②ans=y*(x&1);

y<<=1,x>>=1;

就避免高精度乘除减了(^-^)V;

2.数的遍历匹配

已知一堆数ai,求最少的分组Ai,Bi使得

①Ai∩Bi=∅,Ai∪Bi=U

②对于任意的x,y  ∃i有ax∈Ai而ay∈Bi;

 

最少组数为log amax

分组:Ai为第i位为0的数,Bi为第i位为1的数