预计分数:100+60+0=160
实际分数:100+80+0=180
现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字母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 }
英⽂名称: 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 }
时间限制:
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