The R.I.P of xwzy番外

自个儿在家打3000水题的时候发现了这样一道题:
http://59.61.214.20:3000/problem/show/3003
搞得我大惊失色,本来实现直接跳过,看了看::几何!
用百度翻译了一下,发现:其实不难,我有希望!
结果翻翻题解:看到的是这种无情的*beep*东西!!


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
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <vector>
     
    using namespace std;
    typedef  long double ld;
    const ld eps = 1e-8;
    const int N = 50009;
    struct Point {
        ld x, y;
        Point(ld X = 0, ld Y = 0) { x = X, y = Y; }
        Point operator-(Point a) { return Point(x - a.x, y - a.y); }
        Point operator+(Point a) { return Point(x + a.x, y + a.y); }
        ld operator*(Point a) { return x * a.y - y * a.x; }
        Point operator*(ld a) {return Point(x * a,y * a);}
        ld dis() {
            return sqrt(x * x + y * y);
        }
        void out() {
            printf("%.2Lf %.2Lf\n", x,y);
        }
    } p[N];
    int dcmp(ld a, ld b) {
        if (fabs(a-b)< eps)return 0;
        else if (a > b)return 1;
        else return -1;
    }
    typedef Point Vector;
    struct Line {
        Point p1, p2;
        Vector v;
        //Line(Point P1= {}, Point P2 = {}, Vector V = {}) {p1 = P1, p2=P2, v = V;}
        void out() {
            printf("%.2Lf %.2Lf -> %.2Lf %.2Lf\n", p1.x,p1.y, p2.x, p2.y);
        }
    }L[N];
    void out(ld x) {
        printf("%.2Lf\n", x);
    }
    Point GetCross(Line a, Line b) {
        Vector v = b.p1 - a.p1;
        return b.p1 + (b.v * ((v * a.v) / (a.v * b.v)));
    }
    int cnt[N];
    int n, m;
    void solve() {
        n = 2;
        int p_cnt = 0;
        for (int i = 1; i <= n; i++) {
            ld x1, x2;
            scanf("%Lf%Lf", &x1, &x2);p_cnt++;
            p[p_cnt].x = x1, p[p_cnt].y = x2;
            p[p_cnt] = p[p_cnt];
            scanf("%Lf%Lf", &x1, &x2);
            p_cnt++;
            p[p_cnt].x = x1, p[p_cnt].y = x2;
            p[p_cnt] = p[p_cnt];
            L[i].p1 = p[p_cnt - 1];
            L[i].p2 = p[p_cnt];
            L[i].v = p[p_cnt] - p[p_cnt - 1];
        }
        //out(L[1].v * L[2].v);
        if (dcmp(L[1].v * L[2].v, 0) == 0) {
            Vector v1 = L[2].p1 - L[1].p1;
            if (dcmp(L[1].v * v1, 0) == 0)
            puts("LINE");
            else puts("NONE");
        }  else {
            Point ans = GetCross(L[1], L[2]);
            printf("POINT %.2Lf %.2Lf\n", ans.x, ans.y);
        }
    }
    signed main() {
        puts("INTERSECTING LINES OUTPUT");
        int t = 1;scanf("%d", &t);
        while (t--) {
            solve();
        }
        puts("END OF OUTPUT");
        return 0;
    }

这??

更有甚者

https://blog.csdn.net/Kazama_Kenji/article/details/52202015?utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-1.essearch_pc_relevant&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-1.essearch_pc_relevant

这鸟东西*Beep*是人能看的吗?

四处opeater乱飘,代码可读性极差,也不知道是在写个啥

最后还是有位大佬解释得特清楚,但是我已经找不到他的blog了,这个地儿表达一下对他的感谢。

*第一次使用黄剑锋的模板解题AC

*这辈子见到的第二恶心的题目

AC码


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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//Thanks for Makecpp+ by HJF(Xeon Stin)
//Coded by xwzy
#include<bits/stdc++.h>
//#pragma GCC optimize(3)
#define coor coordinate
using namespace std;

struct coordinate
{
    double x;
    double y;
};

inline void set_file_IO(string);
inline void close_IO(void);
inline int read(void);
inline void work(void);
inline void solve(coor p1, coor p2, coor p3, coor p4);

int main(void) {
    #ifndef ONLINE_JUDGE
        set_file_IO("Intersecting Lines");
    #endif
    //ios::sync_with_stdio(false);
    work();
    #ifndef ONLINE_JUDGE
        close_IO();
    #endif
    return 0;
}
inline void work(void) {
    short delta;
    coordinate p1;
    coordinate p2;
    coordinate p3;
    coordinate p4;
    delta = read();
    printf("INTERSECTING LINES OUTPUT\n");
    while(delta--)
    {
       p1.x = read(); p1.y = read();
       p2.x = read(); p2.y = read();
       p3.x = read(); p3.y = read();
       p4.x = read(); p4.y = read();
       solve(p1, p2, p3, p4);
    }
    printf("END OF OUTPUT\n");
    return;
}
class cross_funs
{
    public:
        inline double isline(coor d1, coor d2, coor d3) {
            return (d3.x - d1.x) * (d2.y - d1.y) - (d3.y - d1.y) * (d2.x - d1.x);
        }
        inline double isparl(coor d1, coor d2, coor d3, coor d4) {
            return (d2.x - d1.x) * (d4.y - d3.y) - (d2.y - d1.y) * (d4.x - d3.x);
        }
        inline double equation_posX(coor p1, coor p2, coor p3, coor p4) {
            double a1 = p1.y - p2.y;
            double b1 = p2.x - p1.x;
            double c1 = p1.x * p2.y - p2.x * p1.y;
            double a2 = p3.y - p4.y;
            double b2 = p4.x - p3.x;
            double c2 = p3.x * p4.y - p3.y * p4.x;
            return (b2 * c1 - b1 * c2) / (b1 * a2 - b2 * a1);
        }
        inline double equation_posY(coor p1, coor p2, coor p3, coor p4) {
            double a1 = p1.y - p2.y;
            double b1 = p2.x - p1.x;
            double c1 = p1.x * p2.y - p2.x * p1.y;
            double a2 = p3.y - p4.y;
            double b2 = p4.x - p3.x;
            double c2 = p3.x * p4.y - p3.y * p4.x;
            return (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
        }
}cross_funs;
inline void solve(coor p1, coor p2, coor p3, coor p4) {
    int cross_f1  = cross_funs.isline(p1, p2, p3);
    int cross_f2  = cross_funs.isline(p1, p3, p4);
    int vector_f1 = cross_funs.isparl(p1, p2, p3, p4);
    if(cross_f1 == 0 and cross_f2 == 0) {
        printf("LINE\n");
        return;
    }
    if(vector_f1 == 0) {
        printf("NONE\n");
        return;
    }  
    else {
        printf("POINT %.2lf " ,cross_funs.equation_posX(p1, p2, p3, p4));
        printf("%.2lf\n"      ,cross_funs.equation_posY(p1, p2, p3, p4));
        return;
    }
}
inline void set_file_IO(string name) {
    freopen((name + ".in" ).c_str(), "r", stdin );
    freopen((name + ".out").c_str(), "w", stdout);
}

inline void close_IO(void) {
    fclose(stdin);
    fclose(stdout);
}
inline int read(void) {
    char ch;
    while (!(isdigit(ch = getchar()) || ch == '-'));
    int res = 0, flg = 1;
    if (ch == '-') flg = -1;
    else res = ch - '0';
    while (isdigit(ch = getchar()))
        (res *= 10) += ch - '0';
    return res * flg;
}

我觉得已经写得很整齐了起码这是人看的。。。

 

线段树

线段树,它功能强大,能区间求和、区间求最值、区间修改等操作。

下面附上代码:


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
97
98
99
100
101
102
103
104
105
106
107
108
//1.建树

sum[10001*4]//线段树
a[10001]    //开始的数据
void build(int l,int r,int k)
{
    if(l==r)                    //到叶子节点
    {
        sum[k] = a[l];
        return ;
    }
    int mid = (l+r)>>1;
    build(l, mid, k<<1);           //分别向左右子树递归
    build(mid+1, r, k<<1|1);
    sum[k] = sum[k<<1] + sum[k<<1|1];    //由两个子节点转移
}
//调用时 ,在输入后用build(1,n,1)     //n为总个数


//2 .单点查询

int ddcx(int l,int r,int k,int x)//x为查询的点的位置
{
    if(l == r)return sum[k];     //到叶子节点
    int mid = (l+r)>>1;
    int ans = 0;                   //记录点的值
    if(x <= mid) ddcx(l, mid, k<<1, x);           //查询的点在mid哪个方向就往那走
    else ddcx (l, mid, k<<1|1, x);
}


//3.单点修改

void ddxg(int l, int r, int k, int x, int y) //x为要修改的点的位置,y为要增加(或减少)的值
{
    if (l == r)                   //到叶子节点 ,修改
    {
        sum[k] += y;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ddxg(l, mid, k << 1, x, y);       //查询的点在mid哪个方向就往那走
    else ddxg(mid + 1, r, k << 1 | 1, x, y);
    sum[k] = sum[k << 1] + sum[k << 1 | 1];          //修改点的值 ,由两个子节点转移  
    return;
}
 
 
//4.区间查询

int qjcx(int l, int r, int k, int x, int y)     //x为区间左侧位置,y为右侧位置
{
    if(l>=x && y>=r) return sum[k];             //若当前区间完全被覆盖,返回节点信息。  
    int mid = (l + r) >> 1;
    int ans = 0;                                  //记录区间值
    if (x <= mid) ans += qjcx(l, mid, k << 1, x, y);             //向两个方向查询
    if (y > mid) ans += qjcx(mid + 1, r, k << 1 | 1, x, y);
    return ans;
}
 
 
//5.区间修改(只修改对查询有用的点)

ad[10001*4]
void add(int l,int r,int k,int v)      //增加(或减少)
{
    ad[k] += v;
    sum[k] += v*(r-l+1);
    return;
}
void pushdown(int l,int r, int k ,int mid)
{
    if(!ad[k])return;
    add(l, mid, k<<1, ad[k]);
    add(mid+1, r, k<<1|1, ad[k]);
    ad[k] = 0;
    return;
}  
int cx(int l,int r,int k,int x,int y)
{
    if(l>=x && y>=r) return sum[k];             //若当前区间完全被覆盖,返回节点信息。  
    int mid = (l + r) >> 1;
    int ans = 0;                                  //记录区间值
    pushdown(l, r, k, mid);            
    if (x <= mid) ans += cx(l, mid, k << 1, x, y);   //向两个方向查询
    if (y > mid) ans += jcx(mid + 1, r, k << 1 | 1, x, y);
    return ans;
}
void change(int l,int r,int k,int x,int y,int v)
//x为要修改的区间左侧位置,y为右侧位置,v为要增加(或减少)的值
{
    if(l>=x && y>=r)
    {
        add(l,r,k,v);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(l, r, k, mid);
    if (x <= mid) change(l, mid, k << 1, x, y, v);   //向两个方向查询
    if (y > mid) change(mid + 1, r, k << 1 | 1, x, y, v);
    sum[k] = sum[k << 1] + sum[k << 1 | 1];          //修改点的值 ,由两个子节点转移  
}
 
 
 
 
 
 

接下来看一下例题:

【例题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
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 10;
int n, m;
long long sum[N];
long long qjcx(int l, int r, int k, int x, int y) {
    if(l>=x&&y>=r) return sum[k];
    int mid = (l + r) >> 1;
    long long s = 0;
    if (x <= mid) s += qjcx(l, mid, k << 1, x, y);
    if (y > mid) s += qjcx(mid + 1, r, k << 1 | 1, x, y);
    return s;
}

void ddxg(int l, int r, int k, int x, int y) {
    if(r < x || x < l) return;
    if (l == r) {
        sum[k] += y;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ddxg(l, mid, k << 1, x, y);
    else ddxg(mid + 1, r, k << 1 | 1, x, y);
    sum[k] = sum[k << 1] + sum[k << 1 | 1];
}

int main() {
    int kk, a, b;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> kk >> a >> b;
        if (!kk) ddxg(1, n, 1, a, b);
        else cout << qjcx(1, n, 1, a, b) << endl;
    }
    return 0;
}

【例题2】区间查改

用上述的区间修改和区间查询。


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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5000010;
ll n, m, a[N];
ll sum[N],ad[N];
void build(ll l,ll r,ll k)
{
    if(l==r)
    {
        sum[k] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, k<<1);
    build(mid+1, r, k<<1|1);
    sum[k] = sum[k<<1] + sum[k<<1|1];
}

void add(ll l,ll r,ll k,ll v)    
{
    ad[k] += v;
    sum[k] += v*(r-l+1);
    return;
}
void pushdown(ll l,ll r, ll k )
{
    if(!ad[k])return;
    ll mid = (l+r)>>1;
    add(l, mid, k<<1, ad[k]);
    add(mid+1, r, k<<1|1, ad[k]);
    ad[k] = 0;
    return;
}  

void change(ll l,ll r,ll k,ll x,ll y,ll v)
{
    if(l>=x && y>=r)
    {
        add(l,r,k,v);
        return;
    }
    pushdown(l, r, k);
    ll mid = (l + r) >> 1;
    if (x <= mid) change(l, mid, k << 1, x, y, v);
    if (y > mid) change(mid + 1, r, k << 1 | 1, x, y, v);
    sum[k] = sum[k << 1] + sum[k << 1 | 1];        
}
long long cx(ll l,ll r,ll k,ll x,ll y)
{
    if(l>=x && y>=r) return sum[k];  
     pushdown(l, r, k);
    ll mid = (l + r) >> 1;  
    ll ans = 0;      
    if (x <= mid) ans += cx(l, mid, k << 1, x, y) ;
    if (y > mid) ans += cx(mid + 1, r, k << 1 | 1, x, y);
    return ans;
}
int main() {
    ll kk, aa, b, v;
    cin >> n >> m;
    for(ll i = 1;i <= n;i++)cin>>a[i];
    build(1,n,1); 
    for (ll i = 1; i <= m; i++)
    {
        cin >> kk >> aa >> b;
        if (kk == 1)
        {
            cin >> v;  
            change(1, n, 1, aa, b, v);
            continue;
        }
        cout << cx(1, n, 1, aa, b) << endl;
    }
    return 0;
}

 

LAST DAY (补写)

爆零直接

第一题

忘记把输出用来测试的删掉了

第二题

“简单DP”

一听到这个名词就知道这题不简单

就是分别判断左儿子和右儿子

特别长的DP

然后改着改着

你就可以把自己绕晕

接着

后面两题

就改不出来了

不过题解上写的倒还是给人看的

第三题

找规律

通过三个柱子推出来

第四题

(⊙o⊙)…

不会了

不懂得该如何去解决它

题解说用差分

但我丝毫看不出来

是我太傻太天真了吗?

八月集训Day8

没有表情包,放张图吧

 

1.好感统计

题解:两个优先队列,将最大的数和最小的数相加,如果可以大于s的话,后面的数相机就都可以大于s,记录当前下标,下一次查找从此开始;如果不可以,就在小数出队,往下一位查找。注意:数不能与自己相加,要去重,并且还有重复相加的,要除以2。以上的查找方式,只需要查找一遍小堆,是O(n)的速度。

 

2.慢跑问题

题解:有向无环图,拓补排序,模板题。(虽然是模板题,但是还没改,普及组的时候很少打图论,我枯了,普及组的时候真应该多学点

 

3.简单操作

题解:输出-1骗了10分,不太懂得怎么打。

 

4.密码

题解:在s1中查找到非连续s2(不只有一个),找到后将其头尾(在s1中s2以前的和s2以后的字符串)进行方案分配。因为方案可以为空,所以第一次查到的需要加1种。

代码好打,注意用char会比string快五倍。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//核心代码

long long t=0;
    int k=0,l=-1;
    for(int i=0,j=0;i<len1&&j<len2;i++)
    {
        if(s1[i]==s2[j])
        {
            if(j==0) { k=l; l=i; }
            if(j==len2-1)
            {
                t+=(long long) (l-k)*(len1-i);
                k=l; j=-1; i=l;
            }
            j++;
        }
    }

 

DAY8

线段树

 

昨天的题目https://www.luogu.com.cn/problem/P3372

void build(int k,int l,int r){

if(l==r){
sum[k]=A[l];
return;
}

int mid=(l+r)/2;

build(k*2,l,mid);

build(k*2+1,mid+1,r);

sum[k]=sum[k*2]+sum[k*2+1];

}//建树

long long query(int k,int l,int r,int x,int y){

if(x<=l&&r<=y)
return sum[k];

int mid=(l+r)/2;

int ans=0;

if(x<=mid)
ans=ans+query(k*2,l,mid,x,y);

if(mid<y)
ans=ans+query(k*2+1,mid+1,r,x,y);

return ans;

}//区间求和

void change(int k,int l,int r,int x,int v){//k父节点编号,x要修改的点,v要加上的值

if(l==r){
sum[k]=sum[k]+v;
return;
}

int mid=(l+r)/2;

if(x<=mid)
change(k*2,l,mid,x,v);
else
change(k*2+1,mid+1,r,x,v);

sum[k]=sum[k*2]+sum[k*2+1];

}//单点修改

but只用单点修改的方法是会超时的

要把单点修改改成区间修改

 

http://noip.ybtoj.com.cn/contest/46/problem/1

一本通oj有单点修改的题目 差不多就是上面模板

 


具体明天见

八月集训Day8

2610. 好感统计

可以用二分查找,for循环累加每个人可能组成的队伍数,(可以先排序,方便查找,查找有个函数可以用)


1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<n;i++)
    {
        u = s-a[i];
        if(a[i]>=s)ans += n-i;
        else if(a[n]>=u)
        {
            j = upper_bound(a+i+1,a+n+1,u)-a;//j为在a数组中下标从i+1到n的第一个大于u的数的下标。
            if(j==n+1)continue;
            ans += n-j+1;
        }
    }

2612. 慢跑问题

本题有负权值,不能用一般的Dijkstra,但是本题有个限制,是要从低往高走,所以可以对Dijkstra稍加修改。

核心代码(Dijkstra):


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
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
ll dis[N],vis[N];
void Dijkstra()
{
    for(ll i=1;i<=n;i++)
        dis[i] = 3e17;
    dis[1] = 0;
    q.push(make_pair(0,1));
    ll u;
    while(!q.empty())
    {
        u = q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(ll i = head[u];i;i = cy[i].next)
        {
            if(dis[cy[i].v] > dis[u]+cy[i].w&&cy[i].v>u)
            {
                dis[cy[i].v] = dis[u]+cy[i].w;
                q.push(make_pair(0,cy[i].v));//只按点的高度排序,不按点的到达距离
            }
        }
    }
    printf("%lld\n",dis[n]);
    if(dis[n]>=0)printf("NO");
    else printf("YES");
}

3255. 密码

不过纯暴力只能过30%

那么正解的暴力就是。
我们记录密码的第一位字母所在原串的位置。
然后在扫描过程中每匹配成功一次,就传导第一位字母所在原串的位置。
并且只要扫描一次就加上最后一位字母所在的位置。
//如果还没有扫到最后一位字母的话就是+0(显然的)

核心代码:


1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=l1;i++)
    {
        f[0]=i;
        for(int j=l2;j>=1;j--)
        {
            if(s2[j]==s1[i])
            {
                f[j]=f[j-1];
            }
        }
        ans+=f[l2];
    }