临海网站制作,宁波seo自然优化技术,ps网页设计培训,济南网站技术预计分数#xff1a;100600160 实际分数#xff1a;100800180 T1 题目描述 现在有一个字符串#xff0c;每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线#xff0c;第三次出现的和四次出现的字母a连一条线#xff0c;第五次出现的和六…预计分数100600160 实际分数100800180 T1 题目描述 现在有一个字符串每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线第三次出现的和四次出现的字母a连一条线第五次出现的和六次出现的字母a连一条线...对其他25个字母也做同样的操作。 现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部另外一个端点在外部。 下图是一个例子共有三对连线交叉我们连线的时候只能从字符串上方经过。 输入格式 一行一个字符串。保证字符串均由小写字母组成且每个字母出现次数为偶数次。 输出格式 一个整数表示答案。 样例输入 abaazooabz 样例输出 3 数据范围 对于30% 的数据字符串长度不超过50。 对于100% 的数据字符串长度不超过100,000。 正解的做法我一开始想到了 但是我感觉时间复杂度应该是O(n^2)于是就没有写 然后自己推了一个很刁钻的做法 首先把每一个节点按照题目的规则从左到右依次编号 把相同编号的两个点的位置看做一条线段 开一棵线段树 每次查询左端点的权值-右端点的权值加到答案里 再在线段树中把当前节点的左右端点之间的权值1 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #define ls k16 #define rs k1|17 using namespace std;8 const int MAXN1000004;9 inline int read()
10 {
11 char cgetchar();int x0,f1;
12 while(c0||c9) {if(c-)f-1;cgetchar();}
13 while(c0c9) xx*10c-48,cgetchar();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 ans0;
24 inline void update(int k)
25 {
26 tree[k].wtree[ls].wtree[rs].w;
27 }
28 inline void down(int k)
29 {
30 tree[ls].w(tree[ls].r-tree[ls].l1)*tree[k].f;
31 tree[rs].w(tree[rs].r-tree[rs].l1)*tree[k].f;
32 tree[ls].ftree[k].f;
33 tree[rs].ftree[k].f;
34 tree[k].f0;
35 }
36 inline void Build_Tree(int ll,int rr,int k)
37 {
38 tree[k].lll;tree[k].rrr;
39 if(tree[k].ltree[k].r){ tree[k].w0;return ; }
40 int midtree[k].ltree[k].r1;
41 Build_Tree(ll,mid,ls);Build_Tree(mid1,rr,rs);
42 update(k);
43 }
44 inline void Point_Ask(int pos,int k)
45 {
46 if(tree[k].ltree[k].r)
47 {
48 anstree[k].w;
49 return ;
50 }
51 if(tree[k].f) down(k);
52 int midtree[k].ltree[k].r1;
53 if(posmid) 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(lltree[k].ltree[k].rrr)
60 {
61 tree[k].w(tree[k].r-tree[k].l1)*val;
62 tree[k].fval;
63 return ;
64 }
65 if(tree[k].f) down(k);
66 int midtree[k].ltree[k].r1;
67 if(llmid) Interval_Add(ll,rr,val,ls);
68 if(rrmid) 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,s1);
76 int nstrlen(s1);
77 Build_Tree(1,n,1);
78 for(int i1;in;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 tot0;
84 for(int i1;in;i)
85 {
86 if(vis[i]1) continue;
87 Point_Ask(i,1);int pans;
88 Point_Ask(nxt[i],1);
89 tottotp-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 11 2 11 3 22 4 23 4 34 5 41 4 12 5 1样例输出2数据范围和约定对于 的数据对于另外 的数据对于 的数据n 1 n 1 nmk4 n,m,q,k n m q k km 3 u,v,w u v w 1 ≤ u,v ≤ n,1 ≤ w ≤ 10 3q 3 x,y,z x y z 1 ≤ x,y ≤ n,1 ≤ z ≤ 10 3−130% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k 030% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k 1100% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,0 ≤ k ≤ 10 直接跑最短路——》30分 枚举走哪一条边——》30分 无视最后的条件跑最短路——》40分 数据太水了没办法。。。。。。 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #includequeue6 using namespace std;7 const int MAXN8004;8 const int INF0x7fffff;9 inline int read()10 {11 char cgetchar();int x0,f1;12 while(c0||c9) {if(c-)f-1;cgetchar();}13 while(c0c9) xx*10c-48,cgetchar();return x*f;14 }15 int n,m,q,k;16 int dis[MAXN];17 int vis[MAXN];18 struct node19 {20 int u,v,w,nxt;21 }edge[MAXN];22 int head[MAXN];23 int num1;24 inline void add_edge(int x,int y,int z)25 {26 edge[num].ux;27 edge[num].vy;28 edge[num].wz;29 edge[num].nxthead[x];30 head[x]num;31 }32 struct node233 {34 int u,v,w,nxt;35 }edge2[MAXN];36 int head2[MAXN];37 int num21;38 inline void add_edge2(int x,int y,int z)39 {40 edge2[num2].ux;41 edge2[num2].vy;42 edge2[num2].wz;43 edge2[num2].nxthead2[x];44 head2[x]num2;45 }46 int SPFA(int S,int T)47 {48 for(int i1;in;i) dis[i]INF;49 dis[S]0;50 queueintq;q.push(S);51 while(q.size()!0)52 {53 int pq.front();q.pop();54 vis[p]0;55 for(int ihead[p];i!-1;iedge[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 queueintq;75 for(int i1;i500;i)76 for(int j1;j4000;j) dp[i][j]INF;77 for(int i1;in;i)78 if(rudu[i]0) q.push(i),dp[i][0]0;79 80 while(q.size()!0)81 {82 int pq.front();q.pop();83 for(int ihead[p];i!-1;iedge[i].nxt)84 for(int j0;jk;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 ihead2[p];i!-1;iedge2[i].nxt)92 for(int j1;jk;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 nread(),mread(),qread(),kread();
106 memset(head,-1,sizeof(head));
107 memset(head2,-1,sizeof(head2));
108 if(kq)
109 {
110 for(int i1;imq;i)
111 {
112 int xread(),yread(),zread();
113 add_edge(x,y,z);
114 }
115 int pSPFA(1,n);
116 if(pINF) printf(-1);
117 else printf(%d,p);
118 }
119 else
120 {
121 for(int i1;im;i)
122 {
123 int xread(),yread(),zread();
124 add_edge(x,y,z);rudu[y];
125 }
126 for(int i1;iq;i)
127 {
128 int xread(),yread(),zread();
129 add_edge2(x,y,z);rudu[y];
130 }
131 if(k0)//一条通道都不能选
132 {
133 int pSPFA(1,n);
134 if(pINF) printf(-1);
135 else printf(%d,p);
136 }
137 else if(k1)
138 {
139 int ansINF;
140 for(int i1;inum2-1;i)//枚举选择那一条边
141 {
142 add_edge(edge2[i].u,edge2[i].v,edge2[i].w);
143 int pSPFA(1,n);
144 if(p!INF) ansmin(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 21 22 33 44 5【样例 1 输出】3【样例 1 解释】三种方案分别为一条高速公路也不关闭关闭城市 2 和城市 3 之间的高速公路关闭城市 3 和城市 4 之间的高速公路。【样例 2 输入】10 21 21 32 42 53 63 73 105 86 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 转载于:https://www.cnblogs.com/zwfymqz/p/7716744.html
