Codeforces Round #375 (Div. 2) Analyses
神他喵难的一场cf
A.The New Year: Meeting Friends
Problems：三个人要走到一个地方，给定x1，x2，x3，问最小代价。
Analysis：思维题，讨论一下就知道答案为max({x1, x2, x3})-min({x1, x2, x3})
Tags:Math, Sorting
Problems：给定一串字符串，只会出现字母，_以及左右括号，问括号外最长的单词长度以及括号内有几个单词
Analysis：一开始以为括号可以嵌套，感觉巨烦，然而，简单模拟
Tags:Implementation
Problems：题面神他喵的烦，其实就是给定一串序列，让你将其修改，使得1-m数目最小的出现次数最大，且修改次数最小
Analysis：首先出现次数的答案是固定的，即n/m（平均分配）。接下去就是分配的问题了，对于那些>m的数，如果存在一个数小于min(m,n/m)，那么就直接修改，否则就不动。之后寻找是否有出现次数<n/m的数，将那些出现次数>n/m的数修改过去就好了
Tags:Greedy
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Low(x) ((x>='a') && (x<='z'))
#define Cap(x) ((x>='A') && (x<='Z'))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
typedef long long ll;
int n, m, a[2010], Cnt[2010], Change;
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v, int w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
int main()
{
read(n); read(m);
for (int i=1; i<=n; i++)
{
read(a[i]);
if (a[i]<=m) Cnt[a[i]]++;
}
for (int i=1; i<=m; i++)
{
int More=(Cnt[i]<(n/m))?(n/m-Cnt[i]):0;
if (More)
for (int j=1; j<=n; j++)
if ((a[j]>m) || (Cnt[a[j]]>n/m))
{
if (a[j]<=m) Cnt[a[j]]--;
a[j]=i; Change++; More--;
if (!More) break;
}
}
printf("%d %d\n", n/m, Change);
for (int i=1; i<=n; i++) printf("%d ", a[i]); puts("");
}
Problems：给你一个地图，其中"*"为sand，"."为lake，一个湖的定义为不和边界有交点并被沙子包围，填湖的代价为湖的面积，求湖的个数<=k的最小代价
Analysis：这题反而水了，直接dfs出湖，sort一下贪心就可以了。
Tags:Greedy, Dfs and similar
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Low(x) ((x>='a') && (x<='z'))
#define Cap(x) ((x>='A') && (x<='Z'))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
typedef long long ll;
struct Data
{
int x, y, Area;
}Lake[10010];
int n, m, k, Map[110][110], Ans, Cnt, Ant;
bool flag;
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v, int w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline bool Cmp(const Data &a, const Data &b) { return a.Area<b.Area; }
inline int dfs(int _x, int _y, int Color)
{
if ((_x<1) || (_x>n) || (_y<1) || (_y>m) || (Map[_x][_y]==Color) || (!Map[_x][_y])) return 0;
if ((_x==1) || (_x==n) || (_y==1) || (_y==m)) { flag=1; return 0; }
Map[_x][_y]=Color;
return dfs(_x-1, _y, Color)+dfs(_x+1, _y, Color)+dfs(_x, _y-1, Color)+dfs(_x, _y+1, Color)+1;
}
int main()
{
scanf("%d%d%d", &n, &m, &k); char x=G_c();
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
x=G_c();
if (x=='.') Map[i][j]=-1;
}
x=G_c();
}
/*for (int i=1; i<=n; i++)
{ for (int j=1; j<=m; j++) printf("%d ", Map[i][j]); puts(""); }*/
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (Map[i][j]==-1)
{
flag=0; int Area=dfs(i, j, ++Cnt);
if (!flag) Lake[Cnt].x=i, Lake[Cnt].y=j, Lake[Cnt].Area=Area;
else Cnt--;
}
sort(Lake+1, Lake+Cnt+1, Cmp);
for (int i=1; i<=Cnt-k; i++) Ans+=Lake[i].Area, dfs(Lake[i].x, Lake[i].y, 0);
printf("%d\n", Ans);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++) if (Map[i][j]) printf("."); else printf("*");
puts("");
}
}
Problems：将一个无向图修改，使得入度==出度的点数尽可能的多，并输出方案
Analysis：首先度数为奇的点必然不是答案，那么Res=n-度数为奇的点，再考虑这些点，每次选择从一个点出发进行修改一条路径（直到另一个奇点），经过的点都走偶数次，直到该点度数为0，即可
Tags:Greedy, Dfs and similar, Graphs
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
typedef long long ll;
struct Data
{
int x, y;
}Edge[40010];
int T, n, m, x, y, Edge_Cnt, Res, In[2010];
int G[2010][2010];
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline void dfs(int u)
{
while (In[u])
{
for (int i=1; i<=n; i++)
if (G[u][i])
{
int v=i;
Edge[++Edge_Cnt].x=u, Edge[Edge_Cnt].y=v;
In[u]--, In[v]--; G[u][v]=G[v][u]=0;
u=v;
break;
}
}
}
int main()
{
read(T);
while (T--)
{
read(n); read(m);
Edge_Cnt=0; Res=n;
for (int i=1; i<=n; i++) { In[i]=0; for (int j=1; j<=n; j++) G[i][j]=0; }
for (int i=1; i<=m; i++)
{
read(x), read(y);
G[x][y]=G[y][x]=1;
In[x]++, In[y]++;
}
for (int i=1; i<=n; i++) Res-=(In[i]&1);
printf("%d\n", Res);
for (int i=1; i<=n; i++)
if (In[i]&1) while (In[i]) dfs(i);
for (int i=1; i<=n; i++) while (In[i]) dfs(i);
for (int i=1; i<=Edge_Cnt; i++) printf("%d %d\n", Edge[i].x, Edge[i].y);
}
}
Problems：给你一张图，求一颗生成树，使得源点s度数不超过ds，汇点t度数不超过dt，并按照输入顺序输出
Analysis：先考虑和s,t无关的点集，每个点集只有三种连法
1. 和s和t均相连：标记
2. 和s或者t中的一个相连：直接和另一个点相连。
3. 孤立点：无法构成要求的生成树
对于这些标记点集，若不和s和t联通，则考虑是否可以将s和t相连，若不可以，则无法构成要求的生成树
剩下的点只需要考虑s或者t相连即可
Tags：Greedy, Dsu, Graphs
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 200010
#define Maxe 800010
typedef long long ll;
vector<int >Point[Maxn];
int n, m, x[Maxe], y[Maxe], To[Maxe], Next[Maxe], Id[Maxe], Head[Maxn], Cnt;
int source, sink, dep_s, dep_t;
int f[Maxn], Ans_s[Maxn], Ans_t[Maxn], Cnt_s, Cnt_t;
bool Used[Maxe];
inline int Get_f(int x) { return (x==f[x])?(x):(f[x]=Get_f(f[x])); }
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
inline void Insert(int u, int v, int w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
int main()
{
read(n); read(m); for (int i=1; i<=n; i++) Head[i]=-1; Cnt=0;
for (int i=1; i<=m; i++)
{
read(x[i]); read(y[i]);
Insert(x[i], y[i], i), Insert(y[i], x[i], i);
}
read(source); read(sink); read(dep_s); read(dep_t);
for (int i=1; i<=n; i++) f[i]=i;
for (int u=1; u<=n; u++)
if ((u^source) && (u^sink))
for (int p=Head[u]; p!=-1; p=Next[p])
{
int v=To[p]; if ((v==source) || (v==sink)) continue;
int Anc_u=Get_f(u), Anc_v=Get_f(v);
if (Anc_u^Anc_v) Used[Id[p]]=1, f[Anc_u]=Anc_v;
}
for (int i=1; i<=n; i++) Point[Get_f(i)].push_back(i);
for (int u=1; u<=n; u++)
if ((u^source) && (u^sink) && (f[u]==u))
{
int Link_source=0, Link_sink=0;
for (int p=0; p<Point[f[u]].size(); p++)
{
int v=Point[u][p];
if (f[v]==u)
{
for (int _p=Head[v]; _p!=-1; _p=Next[_p])
{
int _v=To[_p];
if (_v==source) Link_source=Id[_p]; else if (_v==sink) Link_sink=Id[_p];
}
if ((Link_source) && (Link_sink)) break;
}
}
if ((!Link_source) && (!Link_sink)) { puts("No"); return 0; }
if ((Link_source) && (Link_sink)) Ans_s[++Cnt_s]=Link_source, Ans_t[++Cnt_t]=Link_sink;
else
{
if (Link_source) dep_s--, f[u]=source, Used[Link_source]=1;
if (Link_sink) dep_t--, f[u]=sink, Used[Link_sink]=1;
}
}
if (Cnt_s) dep_s--, dep_t--, Used[Ans_s[1]]=1, Used[Ans_t[1]]=1;
else
{
int Anc=Get_f(1);
for (int i=1; i<=n; i++) if (Get_f(i)^Anc) { Anc=-1; break; }
if (Anc==-1)
{
bool flag=0;
for (int p=Head[source]; p!=-1; p=Next[p])
{
int v=To[p];
if (v==sink) { flag=1; Used[Id[p]]=1; break; }
}
if (!flag) { puts("No"); return 0; }
dep_s--; dep_t--;
f[source]=sink;
}
}
for (int i=2; i<=Cnt_s; i++)
{
if (dep_s) { dep_s--, Used[Ans_s[i]]=1; continue; }
dep_t--, Used[Ans_t[i]]=1;
}
if ((dep_s<0) || (dep_t<0)) { puts("No"); return 0; }
puts("Yes");
for (int i=1; i<=m; i++) if (Used[i]) printf("%d %d\n", x[i], y[i]);
}
Aug 06, 2022 08:17:56 PM
Indian Bank has more than 100 million customers spread all across the world and widely situated mostly throughout India which makes it among few of top banks in our nation. It also has nearly 20,000+ offline branches across Indian which makes their customer service and their facilities much performing that brings the value to the present and the new customers who open their accounts with the bank. Indian Bank Internet Banking I can see that there are many people who find themselves questioning how can I register for Indian bank net banking, and this becomes necessary at one point who do not yet do online banking, because it has become quite necessary with the world advancing
Aug 20, 2022 01:19:21 AM
Kellogg's Family Rewards 2021 :These free Kellogg's Family Rewards codes will help you fill your mailbox with free stuff that you use your points to redeem. This includes free gift cards, toys A LITTLE MORE OF WHAT YOU LOVE. kelloggs family rewards codes 2021 NEW Rice Krispies Treats® Homestyle Original and Chocolate bars are 50% bigger than our 22g Original bar 2021