C. Arthur and Table
Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.
In total the table Arthur bought has n legs, the length of the i-th leg is li.
Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number di — the amount of energy that he spends to remove the i-th leg.
A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5 legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.
Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.
Input
The first line of the input contains integer n (1 ≤ n ≤ 105) — the initial number of legs in the table Arthur bought.
The second line of the input contains a sequence of n integers li (1 ≤ li ≤ 105), where li is equal to the length of the i-th leg of the table.
The third line of the input contains a sequence of n integers di (1 ≤ di ≤ 200), where di is the number of energy units that Arthur spends on removing the i-th leg off the table.
Output
Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.
Sample test(s)
Input
2
1 5
3 2
Output
2
Input
3
2 4 4
1 1 1
Output
0
Input
6
2 2 1 1 3 3
4 3 5 5 2 1
Output
8
思路：枚举长度，找一个最优的
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
const int INF=1000000000;
vector<int> v[maxn];
int d[210];
int len[maxn],cost[maxn];
int N;
int main()
{
scanf("%d",&N);
int x,y;
for(int i=1;i<=N;i++)scanf("%d",&len[i]);
for(int i=1;i<=N;i++)scanf("%d",&cost[i]);
int maxv=0,maxcost=0;
for(int i=1;i<=N;i++)
{
v[len[i]].push_back(i);
d[cost[i]]++;
maxv=max(maxv,len[i]);
maxcost=max(maxcost,cost[i]);
}
int ans=INF;
int before=0;
for(int i=maxv;i>=1;i--)
{
int len=v[i].size();
int sum=0,cnt=0,tmp=0;
int top=N-len*2+1;
for(int j=0;j<len;j++)d[cost[v[i][j]]]--,tmp+=cost[v[i][j]];
if(top>0)
{
for(int j=1;j<=maxcost;j++)
{
if(cnt+d[j]>=top)
{
sum+=j*(top-cnt);
break;
}
else sum+=j*d[j],cnt+=d[j];
}
}
ans=min(ans,before+sum);
N-=len;
before+=tmp;
}
printf("%d\n",ans);
return 0;
}
D. Vitaly and Cycle
After Vitaly was expelled from the university, he became interested in the graph theory.
Vitaly especially liked the cycles of an odd length in which each vertex occurs at most once.
Vitaly was wondering how to solve the following problem. You are given an undirected graph consisting of n vertices and m edges, not necessarily connected, without parallel edges and loops. You need to find t — the minimum number of edges that must be added to the given graph in order to form a simple cycle of an odd length, consisting of more than one vertex. Moreover, he must find w — the number of ways to add t edges in order to form a cycle of an odd length (consisting of more than one vertex). It is prohibited to add loops or parallel edges.
Two ways to add edges to the graph are considered equal if they have the same sets of added edges.
Since Vitaly does not study at the university, he asked you to help him with this task.
Input
The first line of the input contains two integers n and m ( — the number of vertices in the graph and the number of edges in the graph.
Next m lines contain the descriptions of the edges of the graph, one edge per line. Each edge is given by a pair of integers ai, bi (1 ≤ ai, bi ≤ n) — the vertices that are connected by the i-th edge. All numbers in the lines are separated by a single space.
It is guaranteed that the given graph doesn’t contain any loops and parallel edges. The graph isn’t necessarily connected.
Output
Print in the first line of the output two space-separated integers t and w — the minimum number of edges that should be added to the graph to form a simple cycle of an odd length consisting of more than one vertex where each vertex occurs at most once, and the number of ways to do this.
Sample test(s)
Input
4 4
1 2
1 3
4 2
4 3
Output
1 2
Input
3 3
1 2
2 3
3 1
Output
0 1
Input
3 0
Output
3 1
Note
The simple cycle is a cycle that doesn’t contain any vertex twice.
题意：添加t条边，构成奇环，要求t最小，并输出方案数
思路（参考
这里写链接内容
）：要想构成奇环最多添加3条边。首先如果有0条边，那么只要任选3个点就能构成奇环就可以了，方案数是C(N,3)。如果每个节点最多只有一条边相连并且m > 0,那么对于每条边,任选一个节点就可以构成奇环，这时候只需要添加两条边，方案数M*(N-2)。如果存在节点的度大于2,那么用二分图染色判定判断是不是二分图，从而判断有没有奇环（以前写过的
这里写链接内容
）。
如果没有奇环，那么对每个联通分量只需要在同色节点里任选两个加边就能形成奇环，方案数sum(c(ci[0],2)+c(ci[1],2)）；
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100010;
int N,M;
vector<int> edge[maxn];
int vis[maxn];
int cnt[5];
bool judge(int u)
{
int len=edge[u].size();
cnt[vis[u]-1]++;
for(int i=0;i<len;i++)
{
int v=edge[u][i];
if(!vis[v])
{
vis[v]=3-vis[u];
if(judge(v))return true;
}
else if(vis[v]==vis[u])
return true;
}
return false;
}
int main()
{
int u,v;
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++)
{
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
int maxv=0;
for(int i=1;i<=N;i++)
maxv=max(maxv,(int)edge[i].size());
if(maxv==0)
{
printf("3 %I64d\n",LL(N)*(N-1)*(N-2)/6);
return 0;
}
if(maxv==1)
{
printf("2 %I64d\n",(LL)M*(N-2));
return 0;
}
bool odd=0;
LL ans=0;
for(int i=1;i<=N;i++)
{
if(vis[i])continue;
cnt[0]=cnt[1]=0;
vis[i]=1;
if(judge(i))
{
odd=1;
break;
}
ans+=(LL)cnt[0]*(cnt[0]-1)/2;
ans+=(LL)cnt[1]*(cnt[1]-1)/2;
}
if(odd)printf("0 1\n");
else printf("1 %I64d\n",ans);
return 0;
}
E. Ann and Half-Palindrome
Tomorrow Ann takes the hardest exam of programming where she should get an excellent mark.
On the last theoretical class the teacher introduced the notion of a half-palindrome.
String t is a half-palindrome, if for all the odd positions i () the following condition is held: ti = t|t| - i + 1, where |t| is the length of string t if positions are indexed from 1. For example, strings “abaa”, “a”, “bb”, “abbbaa” are half-palindromes and strings “ab”, “bba” and “aaabaa” are not.
Ann knows that on the exam she will get string s, consisting only of letters a and b, and number k. To get an excellent mark she has to find the k-th in the lexicographical order string among all substrings of s that are half-palyndromes. Note that each substring in this order is considered as many times as many times it occurs in s.
The teachers guarantees that the given number k doesn’t exceed the number of substrings of the given string that are half-palindromes.
Can you cope with this problem?
Input
The first line of the input contains string s (1 ≤ |s| ≤ 5000), consisting only of characters ‘a’ and ‘b’, where |s| is the length of string s.
The second line contains a positive integer k — the lexicographical number of the requested string among all the half-palindrome substrings of the given string s. The strings are numbered starting from one.
It is guaranteed that number k doesn’t exceed the number of substrings of the given string that are half-palindromes.
Output
Print a substring of the given string that is the k-th in the lexicographical order of all substrings of the given string that are half-palindromes.
Sample test(s)
Input
abbabaab
7
Output
abaa
Input
aaaaa
10
Output
aaa
Input
bbaabb
13
Output
bbaabb
Note
By definition, string a = a1a2… an is lexicographically less than string b = b1b2… bm, if either a is a prefix of b and doesn’t coincide with b, or there exists such i, that a1 = b1, a2 = b2, … ai - 1 = bi - 1, ai < bi.
In the first sample half-palindrome substrings are the following strings — a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab (the list is given in the lexicographical order).
题意：半回文串指的是对于每个奇数位置i(1=
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=5010;
char s[maxn];
int vis[maxn][maxn];
int K;
struct Trie
{
int ch[maxn*maxn][2];
int val[maxn*maxn];
int sz;
void clear(){memset(ch[0],-1,sizeof(ch[0]));sz=1;}
int idx(char x){return x-'a';}
void insert(char *s,int st)
{
int u=0;
for(int i=st;s[i];i++)
{
int c=idx(s[i]);
if(ch[u][c]==-1)
{
memset(ch[sz],-1,sizeof(ch[sz]));
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
if(vis[st][i]){val[u]++;}
}
}
int process(int u)
{
if(u==-1)return 0;
val[u]+=process(ch[u][0]);
val[u]+=process(ch[u][1]);
return val[u];
}
void find(int u,int k)
{
if(k<1||u==-1)return ;
int cnt1=(ch[u][0]?val[ch[u][0]]:0);
int cnt2=(ch[u][1]?val[ch[u][1]]:0);
int cnt=val[u]-cnt1-cnt2;
if(cnt>=k)return;
k-=cnt;
if(cnt1>=k)
{
printf("a");
find(ch[u][0],k);
}
else
{
k-=cnt1;
printf("b");
find(ch[u][1],k);
}
}
}tree;
int init(char *s)
{
s[0]=' ';
int len=strlen(s)-1;
for(int i=1;i<=len;i++)
{
for(int j=1;j+i-1<=len;j++)
{
vis[j][i+j-1]=(s[j]==s[j+i-1]);
if(i>=5)vis[j][j+i-1]&=vis[j+2][i+j-3];
}
}
return len;
}
int main()
{
scanf("%s%d",s+1,&K);
int n=init(s);
tree.clear();
for(int i=1;i<=n;i++)tree.insert(s,i);
tree.process(0);
tree.find(0,K);
printf("\n");
return 0;
}