2017.10.23解题报告

预计分数:100+60+0=160

实际分数:100+80+0=180

T1

题目描述

现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线,第三次出现的和四次出现的字母a连一条线,第五次出现的和六次出现的字母a连一条线...对其他25个字母也做同样的操作。

现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部,另外一个端点在外部。

下图是一个例子,共有三对连线交叉(我们连线的时候,只能从字符串上方经过)。

输入格式

一行一个字符串。保证字符串均由小写字母组成,且每个字母出现次数为偶数次。

输出格式

一个整数,表示答案。

样例输入

abaazooabz

样例输出

3

数据范围

对于30% 的数据,字符串长度不超过50。

对于100% 的数据,字符串长度不超过100,000。

正解的做法我一开始想到了

但是我感觉时间复杂度应该是O(n^2),于是就没有写

然后自己推了一个很刁钻的做法

首先把每一个节点按照题目的规则,从左到右依次编号

把相同编号的两个点的位置看做一条线段

开一棵线段树

每次查询左端点的权值-右端点的权值,加到答案里

再在线段树中把当前节点的左右端点之间的权值+1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define ls k<<1
 6 #define rs k<<1|1
 7 using namespace std;
 8 const int MAXN=1000004;
 9 inline int read()
10 {
11     char c=getchar();int x=0,f=1;
12     while(c<'0'||c>'9')    {if(c=='-')f=-1;c=getchar();}
13     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
14 }
15 struct node
16 {
17     int l,r,w,f;
18 }tree[MAXN];
19 char s[MAXN];
20 int nxt[MAXN];
21 int pre[MAXN];
22 int vis[MAXN];
23 int ans=0;
24 inline void update(int k)
25 {
26     tree[k].w=tree[ls].w+tree[rs].w;
27 }
28 inline void down(int k)
29 {
30     tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].f;
31     tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].f;
32     tree[ls].f+=tree[k].f;
33     tree[rs].f+=tree[k].f;
34     tree[k].f=0;
35 }
36 inline void Build_Tree(int ll,int rr,int k)
37 {
38     tree[k].l=ll;tree[k].r=rr;
39     if(tree[k].l==tree[k].r){    tree[k].w=0;return ;    }
40     int mid=tree[k].l+tree[k].r>>1;
41     Build_Tree(ll,mid,ls);Build_Tree(mid+1,rr,rs);
42     update(k);
43 }
44 inline void Point_Ask(int pos,int k)
45 {
46     if(tree[k].l==tree[k].r)
47     {
48         ans=tree[k].w;
49         return ;
50     }
51     if(tree[k].f)    down(k);
52     int mid=tree[k].l+tree[k].r>>1;
53     if(pos<=mid)    Point_Ask(pos,ls);
54     else             Point_Ask(pos,rs);
55     update(k);
56 }
57 inline void Interval_Add(int ll,int rr,int val,int k)
58 {
59     if(ll<=tree[k].l&&tree[k].r<=rr)
60     {
61         tree[k].w+=(tree[k].r-tree[k].l+1)*val;
62         tree[k].f+=val;
63         return ;
64     }
65     if(tree[k].f)    down(k);
66     int mid=tree[k].l+tree[k].r>>1;
67     if(ll<=mid)    Interval_Add(ll,rr,val,ls);
68     if(rr>mid)    Interval_Add(ll,rr,val,rs);
69     update(k);
70 }
71 int main()
72 {
73     freopen("cross.in","r",stdin);
74     freopen("cross.out","w",stdout);
75     scanf("%s",s+1);
76     int n=strlen(s+1);
77     Build_Tree(1,n,1);
78     for(int i=1;i<=n;i++)
79     {
80         if(pre[s[i]]==0)    pre[s[i]]=i;
81         if(pre[s[i]])    nxt[pre[s[i]]]=i,pre[s[i]]=i;
82     }
83     long long int tot=0;
84     for(int i=1;i<=n;i++)
85     {
86         if(vis[i]==1)    continue;
87         Point_Ask(i,1);int p=ans;
88         Point_Ask(nxt[i],1);
89         tot=tot+p-ans;
90         Interval_Add(i,nxt[i],1,1);
91         vis[i]=vis[nxt[i]]=1;
92     }
93     printf("%lld",tot);
94     return 0;
95 }

T2跳跳虎回家

英⽂名称: move 时间限制: 1s 空间限制: 256M 题⽬描述 跳跳虎在外⾯出去玩忘了时间,现在他需要在最短的时间内赶回家。 跳跳虎所在的世界可以抽象成⼀个含有 个点的图(点编号从 到 ),跳跳虎现在在 号点,跳跳虎的家在 号点。 图上⼀共有 条单向边,通过每条边有固定的时间花费。 同时,还存在若⼲个单向传送通道,传送通道也有其时间花费。 传送通道⼀般来说⽐普通的道路更快,但是跳跳虎最多只能使⽤ 次。 跳跳虎想知道他回到家的最⼩时间消耗是多少。 输⼊格式 第⼀⾏输⼊ 个整数 ( 表⽰点数, 表⽰普通道路的数量, 表⽰传送通道的数量, 表⽰跳跳虎最多使⽤ 次传送通道) 接下来 ⾏每⾏ 个整数 ,表⽰有⼀条从 到 ,时间花费为 的普通道路( ) 接下来 ⾏每⾏ 个整数 ,表⽰有⼀条从 到 ,时间花费为 的传送通道( ) 输出格式 输出⼀⾏⼀个整数表⽰最⼩时间消耗,如果没法回到家输出 。 样例输⼊ 5 5 2 1 1 2 1 1 3 2 2 4 2 3 4 3 4 5 4 1 4 1 2 5 1 样例输出 2 数据范围和约定 对于 的数据, 对于另外 的数据, 对于 的数据, n 1 n 1 n m k 4 n,m,q,k n m q k k m 3 u,v,w u v w 1 ≤ u,v ≤ n,1 ≤ w ≤ 10 3 q 3 x,y,z x y z 1 ≤ x,y ≤ n,1 ≤ z ≤ 10 3 −1 30% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k = 0 30% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k = 1 100% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,0 ≤ k ≤ 10

直接跑最短路——》30分

枚举走哪一条边——》30分

无视最后的条件跑最短路——》40分

数据太水了没办法。。。。。。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=8004;
  8 const int INF=0x7fffff;
  9 inline int read()
 10 {
 11     char c=getchar();int x=0,f=1;
 12     while(c<'0'||c>'9')    {if(c=='-')f=-1;c=getchar();}
 13     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
 14 }
 15 int n,m,q,k;
 16 int dis[MAXN];
 17 int vis[MAXN];
 18 struct node
 19 {
 20     int u,v,w,nxt;
 21 }edge[MAXN];
 22 int head[MAXN];
 23 int num=1;
 24 inline void add_edge(int x,int y,int z)
 25 {
 26     edge[num].u=x;
 27     edge[num].v=y;
 28     edge[num].w=z;
 29     edge[num].nxt=head[x];
 30     head[x]=num++;
 31 }
 32 struct node2
 33 {
 34     int u,v,w,nxt;
 35 }edge2[MAXN];
 36 int head2[MAXN];
 37 int num2=1;
 38 inline void add_edge2(int x,int y,int z)
 39 {
 40     edge2[num2].u=x;
 41     edge2[num2].v=y;
 42     edge2[num2].w=z;
 43     edge2[num2].nxt=head2[x];
 44     head2[x]=num2++;
 45 }
 46 int SPFA(int S,int T)
 47 {
 48     for(int i=1;i<=n;i++)    dis[i]=INF;
 49     dis[S]=0;
 50     queue<int>q;q.push(S);
 51     while(q.size()!=0)
 52     {
 53         int p=q.front();q.pop();
 54         vis[p]=0;
 55         for(int i=head[p];i!=-1;i=edge[i].nxt)
 56         {
 57             if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
 58             {
 59                 dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
 60                 if(vis[edge[i].v]==0)
 61                 {
 62                     q.push(edge[i].v);
 63                     vis[edge[i].v]=1;
 64                 }
 65             }
 66         }
 67     }
 68     return dis[n];
 69 }
 70 int dp[501][4001];
 71 int rudu[501];
 72 inline void Topsort()
 73 {
 74     queue<int>q;
 75     for(int i=1;i<=500;i++)
 76         for(int j=1;j<=4000;j++)    dp[i][j]=INF;
 77     for(int i=1;i<=n;i++)
 78         if(rudu[i]==0)    q.push(i),dp[i][0]=0;
 79     
 80     while(q.size()!=0)
 81     {
 82         int p=q.front();q.pop();
 83         for(int i=head[p];i!=-1;i=edge[i].nxt)
 84             for(int j=0;j<=k;j++)
 85             {
 86                 dp[edge[i].v][j]=min(dp[edge[i].v][j],dp[i][j]+edge[i].w);
 87                 rudu[edge[i].v]--;
 88                 if(rudu[edge[i].v]==0) q.push(edge[i].v);
 89             }
 90                 
 91         for(int i=head2[p];i!=-1;i=edge2[i].nxt)
 92             for(int j=1;j<=k;j++)
 93             {
 94                 dp[edge[i].v][j]=min(dp[edge[i].v][j],dp[i][j-1]+edge[i].w);
 95                 if(rudu[edge[i].v]==0) q.push(edge[i].v);
 96             }
 97                 
 98     }
 99     printf("%d",dp[n][0]);
100 }
101 int main()
102 {
103     freopen("move.in","r",stdin);
104     freopen("move.out","w",stdout);
105     n=read(),m=read(),q=read(),k=read();
106     memset(head,-1,sizeof(head));
107     memset(head2,-1,sizeof(head2));
108     if(k>=q)
109     {
110         for(int i=1;i<=m+q;i++)
111         {
112             int x=read(),y=read(),z=read();
113             add_edge(x,y,z);
114         }
115         int p=SPFA(1,n);
116         if(p==INF)    printf("-1");
117         else printf("%d",p);
118     }
119     else
120     {
121         for(int i=1;i<=m;i++)
122         {
123             int x=read(),y=read(),z=read();
124             add_edge(x,y,z);rudu[y]++;
125         }
126         for(int i=1;i<=q;i++)
127         {
128             int x=read(),y=read(),z=read();
129             add_edge2(x,y,z);rudu[y]++;
130         }
131         if(k==0)//一条通道都不能选 
132         {
133             int p=SPFA(1,n);
134             if(p==INF)    printf("-1");
135             else printf("%d",p);
136         }
137         else if(k==1)
138         {
139             int ans=INF; 
140             for(int i=1;i<=num2-1;i++)//枚举选择那一条边 
141             {
142                 add_edge(edge2[i].u,edge2[i].v,edge2[i].w);
143                 int p=SPFA(1,n);
144                 if(p!=INF)    ans=min(ans,p);
145                 num--;
146                 head[edge2[i].u]=edge[head[edge2[i].u]].nxt;
147             }
148             printf("%d",ans);
149         }
150         else
151         {
152             Topsort();
153         }
154     }
155     
156     return 0;
157 }

T3秀秀 和哺 噜国 ( cut 

时间限制:

1s空间限制:512MB 【问题描述】 哺噜国里有!个城市,有的城市之间有高速公路相连。在最开始时,哺噜国里有! − 1条高 速公路,且任意两座城市之间都存在一条由高速公路组成的通路。 由于高速公路的维护成本很高, 为了减少哺噜国的财政支出, 将更多的钱用来哺育小哺噜, 秀秀女王决定关闭一些高速公路。 但是为了保证哺噜国居民的正常生活, 不能关闭太多的高速 公路,要保证每个城市可以通过高速公路与至少$个城市(包括自己)相连。 在得到了秀秀女王的指令后,交通部长华华决定先进行预调研。华华想知道在满足每个城 市都可以与至少$个城市相连的前提下,有多少种关闭高速公路的方案(可以一条也不关) 。两 种方案不同, 当且仅当存在一条高速公路在一个方案中被关闭, 而在另外一个方案中没有被关 闭。 由于方案数可能很大, 你只需输出不同方案数对786433取模后的结果即可。 其中786433 = 6×2 -. + 1。 【输入格式】 从文件 cut.in 中读入数据。 输入第一行,包含两个正整数!,$。 接下来的! − 1行,每行包含两个正整数1和2,表示城市1和城市2之间有一条高速公路相 连。 【输出格式】 输出文件到 cut.out 中。 输出一个非负整数,表示所求方案数对 786433 取模后的结果。 【样例 1 输入】 5 2 1 2 2 3 3 4 4 5 【样例 1 输出】 3 【样例 1 解释】 三种方案分别为: 一条高速公路也不关闭; 关闭城市 2 和城市 3 之间的高速公路; 关闭城市 3 和城市 4 之间的高速公路。 【样例 2 输入】 10 2 1 2 1 3 2 4 2 5 3 6 3 7 3 10 5 8 6 9 【样例 2 输出】 12 【子任务】 对于20%的数据:! ≤ 20; 另有30%的数据:! ≤ 100; 另有10%的数据:$ ≤ 100; 另有20%的数据:! ≤ 1000; 对于100%的数据:! ≤ 5000,$ ≤ !。

不会做,

写了个2^n的还被卡了

正解:

考虑用树形??来解决这道问题。 设?[?][?] 表示在?的子树中?所在的连通块大小为?,且其他连通块大小均符合要求的删边方案数 对于每个点?我们一棵一棵地将其子树加进来,设新加入子树的根为? 若删除?与?之间的边,则用?[?][?] * sum(?[?][?]) s \in [k,n] 去更新?[?][?] 若不删?与?之间的边,则枚举?所在连通块的大小?,并更新?[?][?+?] 时间复杂度 O(?^3) ? 考虑一个优化:每次新加一颗子树时,?只需枚举到前面已经加进来的子树大小之和,?也只需枚举到新子树的大小 这只是一个常数优化?其实每个点对相当于只在???处被算了一次 故优化后的时间复杂度是O(?^2)的,本题得以解决。

总结:

这次考得还算可以吧,该拿的分都拿到了

但是这次考试的区分度不是很大

智商性选手比较吃亏,RP行选手比较占优233333

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

单表代替密码原理及算法实现

    要了解单表替代密码就得先了解替代密码,在这里我就做一下简单的介绍:       替代是古典密码中用到的最基本的处理技巧之一 。       替代密码是指...

5456
来自专栏苦逼的码农

从零打卡leetcode之day 3--最大子序列

看到三个for循环,时间复杂度的O(n3)。这速度,实在是太慢了。我们来优化优化。

681
来自专栏Petrichor的专栏

leetcode: 72. Edit Distance

2311
来自专栏chenjx85的技术专栏

leetcode-40-组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

1341
来自专栏谦谦君子修罗刀

程序员面试闪充--UML类图关系

我们曾借白茶清欢等一个人,曾借花开花落叹宠辱不惊。今天借着类图来了解面向对象又有何不可呢? 小视频传送门:小视频传送门 ? 对象模型中,类图是来描述系统的静态结...

40112
来自专栏应兆康的专栏

100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

60610
来自专栏数据结构与算法

2488 绿豆蛙的归宿

2488 绿豆蛙的归宿 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 黄金 Gold 题目描述 Description   随着...

1.2K7
来自专栏冰霜之地

神奇的德布鲁因序列

数学中存在这样一个序列,它充满魔力,在实际工程中也有一部分的应用。今天就打算分享一下这个序列,它在 Google S2 中是如何使用的以及它在图论中,其他领域中...

2133
来自专栏安恒网络空间安全讲武堂

由suctf一道题学到的中国余子式定理

1183
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之从1到n中出现1的次数(九度OJ1373)

题目描述: 亲们!!我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是:求出1~13的...

19510

扫码关注云+社区

领取腾讯云代金券