无聊之举——打题

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的数

初赛考过比较正经的不常用知识点集

https://www.cnblogs.com/fusiwei/p/11559403.html

全国信息学奥林匹克官方网站的网址是https://www.noi.cn/

考场纪律:https://www.noi.cn/gynoi/tlgd/2019-09-30/710458.shtml

复赛可使用C、C++、Pascal语言,2022年后将不可使用Pascal、C语言,只能使用C++。

算术运算符优先级【高到低】:

第一级:圆括号【()】、下标运算符【[]】

第二级:逻辑非运算符【!】、按位取反运算符【~】、自增自减运算符【++ --】、负号运算符【-】、类型转换运算符【(类型)】

第三级:乘法运算符【*】、除法运算符【/】、取余运算符【%】。

第四级:加法运算符【+】、减法运算符【-】。

第五级:左移动运算符【<<】、右移动运算符【>>】。

第六级:关系运算符【< > <= >= 】。

第七级:等于运算符【==】、不等于运算符【!=】。

第八级:按位与运算符【&】。

第九级:按位异或运算符【^】。

第十级:按位或运算符【|】。

第十一级:逻辑与运算符【&&】。

第十二级:逻辑或运算符【||】。

第十三级:条件运算符【?:】。

第十四级:赋值运算符【= += -= *= /= %= >>= <<.= &= |= ^=】。

第十五级:逗号运算符【,】。

逻辑符号

实质等价 A ⇔ B 意味着 A 为真如果 B 为真,和 A 为假如果 B 为假。 x + 5 = y +2 ⇔ x + 3 = y 当且仅当;iff
¬ 逻辑否定 陈述 ¬A 为真,当且仅当 A 为假。 ¬(¬A) ⇔ A
/ 命题逻辑
穿过其他算符的斜线同于在它前面
放置的"¬"。
x ≠ y ⇔ ¬(x = y)
逻辑合取 如果 A 与 B 二者都为真,则陈述 A ∧ B 为真;否则为假。 n < 4 ∧ n >2 ⇔ n = 3(当 n 是自 然数的时候)。
逻辑析取 如果 A 或 B有一个为真陈述 或二者均为真陈述,则 A ∨ B 为真;如果二者都为假,则 陈述为假。 n ≣ 4 ∨ n ≢ 2 ⇔ n ≠ 3(当 n 是 自然数的时候)。
xor 陈述 A ⊕ B 为真,在要么 A 要么 B 但不是二者为真的时候为真。A ⊻ B 意思相同。 (¬A) ⊕ A 总是真,A ⊕ A 总是假。 异或

 

周末训练9.5

拓补排序:https://blog.csdn.net/qq_41713256/article/details/80805338

链式前向星:https://blog.csdn.net/sugarbliss/article/details/86495945

邻接表单向链表->传送门

邻接表:(vector)


1
2
3
4
5
6
7
8
vector<int> G[N];

int u,v;
scanf("%d%d",&u,&v);
G[u].push_back();

for(int i=0;i<G[p].size();i++)
{ int y=G[p][i]; }

快速幂:(模板)


1
2
3
4
5
6
7
8
9
10
11
ll ksm(ll a,ll b)
{
    ll x=1,s=a;
    while(b)
    {
        if(b%2==1) x=(x*s)%m;
        s=(s*s)%m;
        b/=2;
    }
    return x;
}

拓补排序:(有向无环图)


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
//↓T:旅行计划
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1e9;
int n,m;
vector<int> G[N];//邻接表
int rd[N];
queue<int> q;
int ans[N];
int main()
{
//  freopen("plan.in","r",stdin);
//  freopen("plan.out","w",stdout);
   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);//邻接表
        rd[v]++;//记录入度
    }
    for(int i=1;i<=n;i++) if(rd[i]==0) q.push(i),ans[i]=1;//入度为0的入队
    while(!q.empty())
    {
        int p=q.front();q.pop();
        for(int i=0;i<G[p].size();i++)
        {
            int y=G[p][i];//找下一个点
            ans[y]=max(ans[y],ans[p]+1);//DP
            rd[y]--;//入度减一
            if(rd[y]==0) q.push(y);//如果入度为0就入队
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
   
    return 0;
}

 

比赛:

1.排序问题

题解:过两遍sort,注意mod后的赋值

2.阶乘取模

题解:快速幂

3.旅行计划

题解:拓补排序,注意每个点的初值为为1

4.城市重建

题解:邻接表Dijkstra(只能80分)