AtCoder Beginner Contest 173 题解
平均两个月才想起来打一次的abc，结果我还是只能切切四道水题，什么时候我能ak了cf应该就能稳定上蓝了吧。
A - Payment
题意:手上只有若干1000块的钞票，买n块的商品会找多少钱。
数据这么小随便搞搞吧。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=10000000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int main(void)
{
int n;
cin>>n;
int i;
for(i=1000;i<=10000;i+=1000)
{
if(i>=n)
{
cout<<i-n<<endl;
break;
}
}
}
B - Judge Status Summary
题意:把4种字符串计数。
就按题意模拟。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=10000000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int main(void)
{
string s[4]={
"AC","WA","TLE","RE"};
int n;
cin>>n;
int sum[4]={
0};
while(n--)
{
string c;
cin>>c;
int i;
for(i=0;i<4;i++)
if(c==s[i])
sum[i]++;
}
for(int i=0;i<4;i++)
{
cout<<s[i]<<' '<<'x'<<' '<<sum[i]<<endl;
}
}
C - H and V
题意：给一个n x m的矩阵，由’#‘和’.'构成，分别代表黑色和白色，现在你可以任选若干行和若干列将其涂成红色，问有多少种涂法使最终只有k个黑色。
因为n和m都是小于等于6的，所以对于一个6 x 6的矩阵所有情况也就 2^12 种，那就直接爆搜。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
char chess[10][10];
int ans=0;
int n,m,k;
int used[10];
int pp=0;
void dfs(int r,int c,int sum)
{
int i,j;
int num=0;
if(r==n&&c==m)
{
if(pp-sum==k)
ans++;
return;
}
if(r==n)
{
for(i=0; i<n; i++)
{
if(chess[i][c]=='#'&&(!used[i]))
{
num++;
}
}
dfs(r,c+1,sum+num);
dfs(r,c+1,sum);
}
else
{
for(i=0; i<m; i++)
{
if(chess[r][i]=='#')
{
num++;
}
}
used[r]=1;
dfs(r+1,c,sum+num);
used[r]=0;
dfs(r+1,c,sum);
}
}
int main(void)
{
cin>>n>>m>>k;
int i,j;
for(i=0; i<n; i++)
scanf("%s",chess[i]);
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(chess[i][j]=='#')
{
pp++;
}
}
}
dfs(0,0,0);
cout<<ans<<endl;
}
D - Chat in a Circle
题意：现在有一排数字，现在要将这排数字按顺序放入一个圈，每个数字在插入圈时，他的权值就是相邻两个数字中小的那个，第一个插入的人权值为0，问总权值是多少。
既然要让权值最大，那必然要让大的值先插入，否则会被相邻的小的值影响，导致不能贡献权值。以为是一个圈，左右两边都能贡献权值，所以除了最大的数只能贡献一次，剩余的数都可以贡献两次。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
ll a[MAX_N];
bool cmp(ll a,ll b)
{
return a>b;
}
int main(void)
{
int n;
ll sum=0;
cin>>n;
int i;
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+1+n,cmp);
sum+=a[1];
int pos=2;
for(i=2;i<n;i++)
{
if(i%2==0)
sum+=a[pos];
else
sum+=a[pos++];
}
cout<<sum<<endl;
}
F - Intervals on Tree
题意：给你一棵树，节点为1到n，取若干连续编号的节点，求出其连通分量，问所有连续段的连通分量之和。
因为是树，所以一条边必然连接两个连通分量，所以我们可以假设把每个点看成一个连通分量，然后每加入一个边，就把含他的s的数量去掉。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int main()
{
int n;
cin>>n;
ll sum=0;
int l,r;
int i;
for(i=1;i<=n;i++)
{
sum+=(ll)i*(n-i+1);
}
for(i=1;i<n;i++)
{
scanf("%d%d",&l,&r);
if(l>r)
swap(l,r);
sum-=(ll)l*(n-r+1);
}
cout<<sum<<endl;
}
