总结汇总：模板
int getmax_min(char s[])
{//字符串的最大表示法：返回最小数组下标
, j = , k = ;
while(i < len && j < len)
{
k = ;
while(s[i+k] == s[j+k] && k < len) k++;
if(k == len)
return min(i,j);
if (s[i + k] < s[j + k])
> j)
i = i + k + ;
else
i = j + ;
> i)
j = j + k + ;
else
j = i + ;
}
return min(i, j);
}
A题。水题。优先队列。纯模拟。
WA了很久很久的经验教训就是 好好审题 好好写题 把数据范围套串了 简直了
有几个要 注意的wa点
1.不同数据各自的数据范围别看错了
2.审题，最后的最后，是要把所有的朋友都放进来的
3.若两个人同时满足进入条件的时候，价值高的先进，价值相同的，先来的先进。
4.还有还有！！！！队列啊栈啊这种数据结构一定要注意 判空！判空！！！
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
+ ;
int ans[maxn];
struct ss
{
int val,id;
];
bool operator < (const ss& other)const
{
if(val != other.val) return val < other.val;
return id > other.id;
}
}stu[maxn];
struct sss
{
int t,p;
bool operator < (const sss& other)const
{
return t < other.t;
}
}door[maxn];
int main()
{
int T,k,m,q;
scanf("%d",&T);
while(T--)
{
priority_queue<ss>que;
scanf("%d%d%d",&k,&m,&q);
; i <= k; i++)
{
scanf("%s %d", stu[i].name, &stu[i].val);
stu[i].id = i;
}
; i < m; i++)
{
scanf("%d%d", &door[i].t, &door[i].p);
}
sort(door, door + m);
, outid = ;
; i < m; i++)
{
while(stu[cnt].id <= door[i].t && cnt <=k)
{
que.push(stu[cnt]);
cnt++;
}
while((door[i].p--) && (!que.empty()))
{
ss temp = que.top();
que.pop();
ans[ outid ] = temp.id;
outid ++;
}
}
while(cnt <= k)
que.push(stu[cnt++]);
while(!que.empty())
{
ss temp = que.top();
que.pop();ans[ outid ] = temp.id;
outid ++;
}
int x;
; i < q; i++)
{
scanf("%d",&x);
printf()?'\n':' ');
}
}
;
}
题目大意应该是不断的把 连接的池塘少于两个的 池塘移除。最后各个连通分量中，拥有奇数个池塘的价值总和。
怎么解决这个问题呢。相当于移除所有度数小于2的顶点。是用一个类似于。拓扑排序的思路。
d数组：用来记录顶点的度数。vis数组：来标记是否应该被移除。
void toposort()
{
queue<int>que;
;i<=n;i++)
)
{
vis[i] = ;
que.push(i);
}
while(!que.empty())
{
int t = que.front();que.pop();
;i<G[t].size();i++)
{
int v = G[t][i];
)
{
d[v]--;
)
{
vis[v] = ;
que.push(v);
}
}
}
}
}
那如何统计。各个连通分量中的顶点个数呢，用dfs。搜索。
另外就是注意！sum的类型应该是LL的。高亮部分叠加的时候，要注意val数组是int型的。
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
+ ;
int n,m,T,x,y,d[maxn],vis[maxn],val[maxn];
LL sum,amount;
vector<int>G[maxn];
void toposort()
{
queue<int>que;
;i<=n;i++)
)
{
vis[i] = ;
que.push(i);
}
while(!que.empty())
{
int t = que.front();que.pop();
;i<G[t].size();i++)
{
int v = G[t][i];
)
{
d[v]--;
)
{
vis[v] = ;
que.push(v);
}
}
}
}
}
void dfs(int s)
{
vis[s] = ;
;i<G[s].size();i++)
{
int v = G[s][i];
)
{
amount++;
sum = sum + (LL)val[v];
dfs(v);
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(d,,sizeof(d));
memset(vis,,sizeof(vis));
;i<=maxn;i++)
G[i].clear();
scanf("%d%d",&n,&m);
;i<=n;i++)
scanf("%d",&val[i]);
;i<m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
d[x]++, d[y]++;
}
toposort();
LL tot = ;
;i<=n;i++)
{
)
{//说明未被删除
sum = val[i];
amount = ;
dfs(i);
== )
tot = tot + sum;
}
}
printf("%lld\n",tot);
}
}
注意一下题意就好了，它不是让你求最短路，是每段小于那个给出的值就可以了。
在这张图上，权值小于等于给定值的路，相关的顶点有一个c（n，2）的组合。也就是n*(n-1)/2
在并查集里加一个数组记录一下这个并查集里面的结点的总数就行了。
哦对了，这里最关键的是，利用离线处理，而不是在线处理来提高效率。
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
#define mem0(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,-1,sizeof(x))
+ ;
struct QQ
{
int w,id;
bool operator <(const QQ& other)
{
return w < other.w;
}
}Q[+];
+ ];
struct edge
{
int x,y,w;
bool operator <(const edge& other)
{
return w < other.w;
}
}es[ + ];
int pa[maxn], num[maxn];
void init(int n)
{
;i<=n;i++)
pa[i] = i, num[i] = ;
}
int uf_find(int x){return x == pa[x] ? x : (pa[x] = uf_find(pa[x]));}
void join(int x,int y)
{
int fx = uf_find(x);int fy = uf_find(y);
if(fx != fy)
pa[fx] = fy, num[fy] += num[fx];
}
int main()
{
int T,n,m,q;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d", &n, &m, &q);
init(n);
;i<m;i++)
{
scanf("%d%d%d", &es[i].x, &es[i].y, &es[i].w);
}
sort(es, es + m);
;i<q;i++)
{
scanf("%d",&Q[i].w);
Q[i].id = i;
}
sort(Q, Q + q);
, j = ;
;i<q;i++)
{
while(j < m && es[j].w <= Q[i].w)
{
int fx = uf_find(es[j].x);
int fy = uf_find(es[j].y);
j++;
if(fx == fy) continue;
cnt += (num[fx] + num[fy]) * (num[fx] + num[fy] - )
-num[fx] * (num[fx] - )
-num[fy] * (num[fy] - );
join(fx,fy);
}
ans[ Q[i].id ] = cnt;
}
; i < q; i++)
{
printf("%d\n",ans[i]);
}
}
;
}
这道题。字符串的最大表示法。
getmax_min函数是最大表示中取最小的数组下标，_max就是取最大的数组下标。
要有一步，预处理：
; i < len; i++)
{
ss[*len-i-] = ss[len-i-] = s[i+len] = s[i];
}
ss[*len] = *len] = '\0';//容易遗漏
然后把，表示出来的两个字符串放到两个新的数组中保存。
; i < len; i++)
{
s_0[i] = s[ans_0+i];
s_1[i] = ss[ans_1+i];
}
s_0[len] = s_1[len] = '\0';
接下来就是根据题意进行一些列判定和输出就行了。
主干代码在两个函数上。
需要注意的地方，都有高亮了。
第二个函数中k == len之后的处理，很关键，是哪来找循环节的，不然算法会退化到n²。
其他的怎么理解，昂，只能自己画图吧，画着画着就懂了吧。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
+ ;
*maxn], ss[*maxn], s_0[maxn], s_1[maxn];
int T,len;
int getmax_min(char s[])
{
, j = , k = ;
while(i < len && j < len)
{
k = ;
while(s[i+k] == s[j+k] && k < len) k++;
if(k == len)
return min(i,j);
if (s[i + k] < s[j + k])
> j)
i = i + k + ;
else
i = j + ;
> i)
j = j + k + ;
else
j = i + ;
}
return min(i, j);
}
int getmax_max(char s[])
{
, j = , k= ;
while(i < len && j < len)
{
k = ;
while(s[i + k] == s[j + k] && k < len) k++;
if (k == len)
{
int loop = abs(i - j);
return len - loop + i;
}
else
{
if (s[i + k] < s[j + k])
> j)
i = i + k + ;
else
i = j + ;
> i)
j = j + k + ;
else
j = i + ;
}
}
if(j >= len)
return i;
return j;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&len);
scanf("%s",s);
; i < len; i++)
{
ss[*len-i-] = ss[len-i-] = s[i+len] = s[i];
}
ss[*len] = *len] = '\0';
int ans_0 = getmax_min(s);
int ans_1 = getmax_max(ss);
; i < len; i++)
{
s_0[i] = s[ans_0+i];
s_1[i] = ss[ans_1+i];
}
s_0[len] = s_1[len] = '\0';
int p = strcmp(s_0, s_1);
)
{
printf();
}
)
{
printf("%d 1\n", len - ans_1);
}
else
{
< len - ans_1)
{
printf();
}
else
{
printf("%d 1\n", len - ans_1);
}
}
}
;
}
裸的线段树（建树+区间和查询）。。。。没啥说的，模板题。
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
#define mem0(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,-1,sizeof(x))
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
;
];
], MAX[rt << | ]);}
void build(int l,int r,int rt)
{
if(l == r) {scanf("%d",&MAX[rt]);return ;}
;
build(lson), build(rson);
pushup(rt);
}
int query(int ll,int rr,int l,int r,int rt)
{
if(ll <= l && rr >= r) return MAX[rt];
;
;
if(ll <= m )
ans = max(ans, query(ll,rr,lson));
if(rr > m)
ans = max(ans, query(ll,rr,rson));
return ans;
}
int main()
{
int t, x, y, m, n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
build(,n,);
scanf("%d",&m);
;i<m;i++)
{
scanf("%d%d",&x,&y);
,n,);
printf("%d\n",ans);
}
}
;
}
！！！其实就是个，给树的中序遍历和前序遍历的结果，构造个树。。然后dfs一下就好了。如果看出来是 中序+前序 这题就变得非常水了。
#include <cstdio>
],];
struct A
{
int left,right;
}node[];
int build(int l1,int r1,int l2,int r2)
{
;
int root = pre[l2];
int p = l1;
while(in[p] != root) p++;
int cnt = p - l1;
node[root].left = build(l1, l1+cnt-,l2+,l2+cnt);
node[root].right = build(l1+cnt+,r1,l2+cnt+,r2);
return root;
}
void dfs(int x,int root)
{
)
{
printf("E"),dfs(x,node[root].left);
}
)
printf("W"),dfs(x,node[root].right);
else
return ;
}
int main()
{
int T,n,m;
scanf("%d", &T);
while(T--)
{
scanf("%d",&n);
; i <= n; i++)
scanf("%d",&pre[i]),in[i] = i;
,n,,n);
scanf("%d",&m);
; i < m; i++)
{
int x;
scanf("%d",&x);
dfs(x,root);
puts("");
}
}
;
}