大学ACM第一周心得

PS：因为旨在复习，所以其实是每个专题挑些题目的（一般挑提高上下）

然后又只写了错了比较多次的题，所以就都不是一个算法的了。

T1：USACO Training 1.1.1 Your Ride Is Here

　　WA的原因：

　　　　1.看错题意：“举例来说，团体 "USACO" 会是 21191315=17955” 这句话当时忽略了，以为就是把字符串转成数字，再取模就行了（甚至还改了longlong，循环里取模等）浪费挺多时间的，下次一定要看懂题目。

　　　　2.看懂题目后，有的变量的初始化没有改。贴个没有改前的代码：

 1 #include<bits/stdc++.h> 
 2 #define ll long long
 3 #define inf 0x7fffff
 4 #define N 500010
 5 #define lson rt<<1
 6 #define rson rt<<1|1
 7 #define FR freopen("tset.in","r",stdin)
 8 #define FW freopen("test.out","w",stdout)
 9 using namespace std;
10 ll read()
11 {
12     ll x=0;int f=1;char ch=getchar();
13     while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
14     while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 
18 char a[10],b[10];
19 int ansa=0,ansb=0;
20 int main()
21 {
22     scanf("%s%s",&a,&b);
23     int c=strlen(a),d=strlen(b);
24     for (int i=0;i<c;i++)
25     {
26         int x=a[i]-'A'+1;
27         ansa=(ansa*x)%47;
28     }
29     for (int i=0;i<d;i++)
30     {
31         int x=b[i]-'A'+1;
32         ansb=(ansb*x)%47;
33     }
34     // cout<<ansa<<endl<<ansb<<endl;
35     // ansa%=47,ansb%=47;
36     if (ansa==ansb) printf("GO");
37     else printf("STAY");
38     return 0;
39 }

View Code

　　　　第19行ansa，ansb的初始化还是原来的，这里应该改成1；

T2：洛谷P3743kotori的设备

　　我看了贼久题目，感觉现在读题能力真的差的不行。而且一直以为充电宝一定要在整个单位时间给某一个设备充电，怎么都没懂样例，原来充电宝可以随便给一台设备充多久，0.0000001s都行。所以，看题目标签（不小心看到了嗷）是个二分，那就很好想了，上代码叭（但是精度还是有点坑，一般还是尽量精确吧）

#include<bits/stdc++.h> 
#define ll long long
#define inf 1e10
#define N 500010
#define lson rt<<1
#define rson rt<<1|1
#define FR freopen("tset.in","r",stdin)
#define FW freopen("test.out","w",stdout)
using namespace std;
ll read()
{
    ll x=0;int f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
double a[100010],b[100010],n;
double sum,p;
bool check(double ans)
{
    double tot=p*ans;
    sum=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]*ans<=b[i]) continue;
        sum+=(a[i]*ans-b[i]);
    }
    return sum<=tot;
}
int main()
{
    n=read(),p=read();
    for (int i=1;i<=n;i++)
    {
        a[i]=read();b[i]=read();
        sum+=a[i];
    }
    if (sum<=p) 
    {
        printf("-1"); 
        return 0;
    }
    double l=0,r=1e10;
    while (r-l>1e-6)
    {
        double mid=(l+r)/2;
        if (check(mid)) l=mid;
        else r=mid;
    }
    printf("%.6lf",l);
    return 0;
}

View Code

T3：洛谷P1825[USACO11OPEN]Corn Maze S

　　很明显的搜索。代码：

 1 #include<bits/stdc++.h> 
 2 #define ll long long
 3 #define inf 1e10
 4 #define N 350
 5 #define lson rt<<1
 6 #define rson rt<<1|1
 7 #define FR freopen("tset.in","r",stdin)
 8 #define FW freopen("test.out","w",stdout)
 9 using namespace std;
10 ll read()
11 {
12     ll x=0;int f=1;char ch=getchar();
13     while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
14     while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 
18 struct node
19 {
20     int x;
21     int y;
22     int stp;
23 };
24 queue<node> q;
25 char a[N][N];
26 bool vis[N][N];
27 int n,m;
28 int dx[4]={1,0,-1,0};
29 int dy[4]={0,1,0,-1};
30 int sx,sy;
31 void gto(int &nx,int &ny,int k)
32 {
33     for (int i=1;i<=n;i++)
34     {
35         for (int j=1;j<=m;j++)
36         {
37             if (a[i][j]==a[nx][ny]&&(i!=nx||j!=ny))
38             {
39                 nx=i;
40                 ny=j;
41                 return ;
42             }
43         }
44     }
45 }
46 int main()
47 {
48     n=read(),m=read();
49     for (int i=1;i<=n;i++)
50     {
51         for (int j=1;j<=m;j++)
52         {
53             char ch;
54             // ch=getchar();
55             cin>>ch;
56             a[i][j]=ch;
57             if (ch=='@')
58             {
59                 sx=i;
60                 sy=j;
61             }
62         }
63     }
64     vis[sx][sy]=true;
65     q.push((node){sx,sy,0});
66     while (!q.empty())
67     {
68         node now=q.front();
69         q.pop();
70         if (a[now.x][now.y]=='=')
71         {
72             printf("%d",now.stp);
73             return 0;
74         }
75         if (a[now.x][now.y]>='A'&&a[now.x][now.y]<='Z')
76         {
77             gto(now.x,now.y,now.stp);
78         }
79         for (int i=0;i<4;i++)
80         {
81             int nx=now.x+dx[i];
82             int ny=now.y+dy[i];
83             if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&!vis[nx][ny])
84             {
85                 vis[nx][ny]=true;
86                 q.push((node){nx,ny,now.stp+1});
87             }
88         }
89     }
90     return 0;
91 }

完整代码

复习起了一个点是，在函数参数前加‘&’，那在函数里对值做的修改都会返回原函数。比如代码里的：

 1 void gto(int &nx,int &ny,int k)
 2 {
 3     for (int i=1;i<=n;i++)
 4     {
 5         for (int j=1;j<=m;j++)
 6         {
 7             if (a[i][j]==a[nx][ny]&&(i!=nx||j!=ny))
 8             {
 9                 nx=i;
10                 ny=j;
11                 return ;
12             }
13         }
14     }
15 }

View Code

T4:洛谷P5076 【深基16.例7】普通二叉树（简化版）

　　给一道绿题跪了。。。因为之前刚好花了一下午复习splay（顺便贴一个splay模板）

  1 #include<bits/stdc++.h> 
  2 #define ll long long
  3 #define inf 1e10
  4 #define N 100010
  5 #define lson rt<<1
  6 #define rson rt<<1|1
  7 #define FR freopen("tset.in","r",stdin)
  8 #define FW freopen("test.out","w",stdout)
  9 using namespace std;
 10 ll read()
 11 {
 12     ll x=0;int f=1;char ch=getchar();
 13     while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
 14     while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 int ch[N][2],sz[N],cnt[N],key[N],f[N],rt,tot,n;
 18 int pd(int x) 
 19 {
 20     return ch[f[x]][1]==x;
 21 }
 22 void update(int x)
 23 {
 24     if (x)
 25     {
 26         sz[x]=cnt[x];
 27         if (ch[x][0]) sz[x]+=sz[ch[x][0]];
 28         if (ch[x][1]) sz[x]+=sz[ch[x][1]];
 29     }
 30 }
 31 void clear(int x)
 32 {
 33     ch[x][0]=ch[x][1]=f[x]=cnt[x]=sz[x]=key[x]=0;
 34 }
 35 void rotate(int x)
 36 {
 37     int fa=f[x],ffa=f[fa],dir=pd(x);
 38     ch[fa][dir]=ch[x][dir^1];f[ch[x][dir^1]]=fa;
 39     ch[x][dir^1]=fa;f[fa]=x;
 40     f[x]=ffa;
 41     if (ffa) ch[ffa][ch[ffa][1]==fa]=x;
 42     update(x);update(fa);
 43 }
 44 void Spl(int x)
 45 {
 46     int fa=f[x];
 47     while (fa)
 48     {
 49         if (f[fa]) rotate(pd(x)==pd(fa)?fa:x);
 50         rotate (x);rt=x;fa=f[x];
 51     }
 52 }
 53 void insert(int x)
 54 {
 55     if (rt==0)
 56     {
 57         f[++tot]=0;
 58         ch[tot][0]=ch[tot][1]=0;
 59         key[tot]=x;rt=tot;
 60         sz[tot]=cnt[tot]=1;
 61         return ;
 62     }
 63     int nw=rt,fa=0;
 64     while(1)
 65     {
 66         if (x==key[nw])//这个值之前存在
 67         {
 68             cnt[nw]++;
 69             update(nw);
 70             update(fa);
 71             Spl(nw);break;
 72         }
 73         fa=nw;nw=ch[nw][x>key[nw]];
 74         if (nw==0)//这个值之前不存在
 75         {
 76             f[++tot]=fa;
 77             ch[fa][x>key[fa]]=tot;
 78             ch[tot][1]=ch[tot][0]=0;
 79             key[tot]=x;
 80             sz[tot]=cnt[tot]=1;
 81             update(fa);Spl(tot);
 82             break;
 83         }
 84     }
 85 }
 86 int ask1(int x)
 87 {
 88     int nw=rt,res=0;
 89     while(1)
 90     {
 91         if (x<key[nw]) nw=ch[nw][0];
 92         else
 93         {
 94             if (ch[nw][0]) res+=sz[ch[nw][0]];
 95             if (x==key[nw])
 96             {
 97                 Spl(nw);
 98                 return res+1;
 99             }
100             else res+=cnt[nw],nw=ch[nw][1];
101         }
102     }
103 }
104 int ask2(int x)
105 {
106     int nw=rt;
107     while (1)
108     {
109         if (ch[nw][0]&&x<=sz[ch[nw][0]])
110             nw=ch[nw][0];
111         else
112         {
113             if (ch[nw][0]) x-=sz[ch[nw][0]];
114             if (x<=cnt[nw]) return key[nw];
115             else {x-=cnt[nw];nw=ch[nw][1];}
116         }
117     }
118 }
119 int getpre()
120 {
121     int nw=ch[rt][0];
122     while (ch[nw][1]) nw=ch[nw][1];
123     return nw;
124 }
125 int getnex()
126 {
127     int nw=ch[rt][1];
128     while (ch[nw][0]) nw=ch[nw][0];
129     return nw;
130 }
131 void del(int x)
132 {
133     ask1(x);
134     if (cnt[rt]>1)
135     {
136         cnt[rt]--;
137         update(rt);
138         return ;
139     }
140     if (!ch[rt][0]&&!ch[rt][1])
141     {
142         clear(rt);
143         rt=0;
144         return ;
145     }
146     if (!ch[rt][0])
147     {
148         int old=rt;rt=ch[rt][1];
149         f[rt]=0;
150         clear(old);
151         return ;
152     }
153     if (!ch[rt][1])
154     {
155         int old=rt;rt=ch[rt][0];
156         f[rt]=0;
157         clear(old);
158         return ;
159     }
160     int pre=getpre(),old=rt;
161     Spl(pre);
162     ch[rt][1]=ch[old][1];
163     f[ch[old][1]]=rt;
164     clear(old);
165     update(rt);
166 }
167 int main()
168 {
169     n=read();
170     while (n--)
171     {
172         int ty=read(),x=read();
173         if (ty==1) insert(x);
174         if (ty==2) del(x);
175         if (ty==3) printf("%d
",ask1(x));
176         if (ty==4) printf("%d
",ask2(x));
177         if (ty==5) 
178         {
179             insert(x);
180             printf("%d
",key[getpre()]);
181             del(x);
182         }
183         if (ty==6) 
184         {
185             insert(x);
186             printf("%d
",key[getnex()]);
187             del(x);
188         }
189     }
190 }

splay模板（洛谷）

　　然后就想无脑打splay来着，结果全部TLE了。。目前猜测原因是题目有个坑：操作一要查询的值x不一定在平衡树里，这个查询会死循环。但是我并没有改好（对不起我太菜了）所以就直接用STL了，正解：

 1 #include<bits/stdc++.h> 
 2 #define ll long long
 3 #define inf 1e10
 4 #define N 100010
 5 #define lson rt<<1
 6 #define rson rt<<1|1
 7 #define FR freopen("tset.in","r",stdin)
 8 #define FW freopen("test.out","w",stdout)
 9 using namespace std;
10 ll read()
11 {
12     ll x=0;int f=1;char ch=getchar();
13     while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
14     while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 int q,n,a[N];
18 int main()
19 {
20     q=read();
21     while (q--)
22     {
23         int ty=read(),x=read();
24         if (ty==1) 
25         {
26             int tmp=lower_bound(a+1,a+n+1,x)-a;
27             printf("%d
",tmp);
28         }
29         if (ty==2) printf("%d
",a[x]);
30         if (ty==3)
31         {
32             int tmp=lower_bound(a+1,a+n+1,x)-a;
33             printf("%d
",a[tmp-1]);
34         }
35         if (ty==4)
36         {
37             int tmp=upper_bound(a+1,a+n+1,x)-a;
38             if (tmp!=n+1) printf("%d
",a[tmp]);
39             else printf("2147483647
");
40         }
41         if (ty==5)
42         {
43             int tmp=lower_bound(a+1,a+n+1,x)-a;
44             if (tmp==n+1) a[++n]=x;
45             else
46             {
47                 for (int i=n;i>=tmp;i--)
48                 a[i+1]=a[i];a[tmp]=x;
49                 n++;
50             }
51         }
52     }
53     return 0;
54 }

View Code

数论专题专门另外写了篇博客，还在学习中：https://www.cnblogs.com/71-111/p/9745026.html