Codeforces Round #513 游记
A - Phone Numbers
题目大意：
电话号码是8开头的\(1\)位数字。告诉你\(n(n\le100)\)个数字，每个数字至多使用一次。问最多能凑出多少个电话号码。
思路：
统计8出现的次数，如果有多余的8不能作为开头，那么就将其放到后面去
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
inline int getdigit() {
register char ch;
while(!isdigit(ch=getchar()));
return ch^'0';
}
int cnt[2];
int main() {
const int n=getint();
for(register int i=0;i<n;i++) cnt[getdigit()==8]++;
while(cnt[0]<cnt[1]*10) {
cnt[1]--;
cnt[0]++;
}
printf("%d\n",std::min(cnt[1],cnt[0]/10));
return 0;
}
B - Maximum Sum of Digits
题目大意：
定义\(S(x)\)为\(x\)各数位之和。给定\(n(n\le10^{12})\)，\(a+b=n\)，求\(S(a)+S(b)\)的最大值。
思路：
如果这一位\(x\)不是第一位，且这一位不是\(9\)，就把这一位当做\(10+x\)，并把上一位\(-1\)。
源代码：
#include<cstdio>
#include<cctype>
typedef long long int64;
inline int64 getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int64 x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
int main() {
int64 n=getint();
int ans=0;
for(;n;n/=10) {
ans+=n%10;
if(n%10!=9&&n/10!=0) {
ans+=10;
n-=10;
}
}
printf("%d\n",ans);
return 0;
}
C - Maximum Subrectangle
题目大意：
给定\(a_{1\sim n}，b_{1\sim m}(n,m\le2000)\)和\(x\)，\(c_{i,j}=a_ib_j\)。求\(c\)的一个最大子矩阵，使得矩阵内数字和\(\le x\)。输出面积的最大值。
思路：
预处理\(a/b\)连续\(i\)个数之和的最小值。然后枚举矩形长宽即可。
源代码：
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=2001;
int a[N],b[N],min1[N],min2[N];
int main() {
const int n=getint(),m=getint();
for(register int i=1;i<=n;i++) a[i]=getint();
for(register int i=1;i<=m;i++) b[i]=getint();
const int x=getint();
for(register int i=1;i<=n;i++) {
min1[i]=INT_MAX;
int sum=0;
for(register int j=1;j<i;j++) sum+=a[j];
for(register int j=i;j<=n;j++) {
sum-=a[j-i];
sum+=a[j];
min1[i]=std::min(min1[i],sum);
}
}
for(register int i=1;i<=m;i++) {
min2[i]=INT_MAX;
int sum=0;
for(register int j=1;j<i;j++) sum+=b[j];
for(register int j=i;j<=m;j++) {
sum-=b[j-i];
sum+=b[j];
min2[i]=std::min(min2[i],sum);
}
}
int ans=0;
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=m;j++) {
if((int64)min1[i]*min2[j]<=x) {
ans=std::max(ans,i*j);
}
}
}
printf("%d\n",ans);
return 0;
}
D - Social Circles
题目大意：
有\(n(n\le10^5)\)个人排成一圈，第\(i\)个人要求自己左边空出\(l_i\)个座位，右边空出\(r_i(l_i,r_i\le10^9)\)个座位。问最少需要安排多少个座位。
思路：
一开始先假设每个人都占了\(l_i+r_i+1\)个位置。考虑怎样安排相邻人的顺序，并合并相邻人的\(l_i,r_i\)使得答案最优。
将所有\(l_i,r_i\)分别排序，将对应的\(l_i,r_i\)合并一定是最优的（想一想这是为什么）。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=1e5+1;
int l[N],r[N];
int main() {
const int n=getint();
int64 ans=0;
for(register int i=1;i<=n;i++) {
l[i]=getint();
r[i]=getint();
ans+=l[i]+r[i]+1;
}
std::sort(&l[1],&l[n]+1);
std::sort(&r[1],&r[n]+1);
for(register int i=1;i<=n;i++) {
ans-=std::min(l[i],r[i]);
}
printf("%lld\n",ans);
return 0;
}
E - Sergey and Subway
题目大意：
给定一棵\(n(n\le2\times10^5)\)个点的树，每条边权都是\(1\)。原树上的边称作老边，两个点之间可以连一条新边当且仅当原来两个点之间距离为\(2\)。问最后所有点对之间最短路之和是多少？
思路：
首先不考虑新边，我们可以考虑每条边的贡献计算出所有点对距离值和\(sum\)。
而经过加新边的操作后，原来距离为偶数的点对距离\(/2\)，奇数点对距离\(/2+1\)。而我们可以通过黑白染色后黑/白点的数目统计出奇数距离的点对数目。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
using int64=long long;
const int N=2e5+1;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
int64 ans;
bool col[N];
int n,size[N],cnt[2],par[N];
void dfs(const int &x,const int &par) {
size[x]=1;
::par[x]=par;
cnt[col[x]=!col[par]]++;
for(auto &y:e[x]) {
if(y==par) continue;
dfs(y,x);
size[x]+=size[y];
ans+=(int64)size[y]*(n-size[y]);
}
}
int main() {
n=getint();
for(register int i=1;i<n;i++) {
add_edge(getint(),getint());
}
dfs(1,0);
ans=(ans+(int64)cnt[0]*cnt[1])/2;
printf("%lld\n",ans);
return 0;
}