K.Class
思路：水题秒之。
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
long long int a = (x+y)/2;
long long int b = (x-y)/2;
cout<<a*b<<endl;
return 0;
}
J. Worker
思路：我们仔细分析一下题意，给了n个厂，m个人，假设每个厂的福利原因使得工人的工作能力不同，然后你要把这m个人分给n个厂，使得每个厂的总效益相同。给厂分人，肯定是福利不好效益低的厂多分几个人，然后效益高的人少。如何实现这个决策呢？***求最小公倍数！！！***所有厂效益的最小公倍数，然后用这个最小公倍数挨个求得是每个厂效益的多少倍并累加。如果工人数对这个倍数取余 == 0；则说明可以实现这样的一种分配！
#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
typedef long long LL;
LL n,m;
LL a[maxn],b[maxn];
int gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
int lcm(LL a,LL b)
{
return (a*b)/gcd(a,b);
}
int main()
{
while(~scanf("%lld %lld",&n,&m))
{
LL flag=1;
for(LL i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
flag=lcm(max(flag,a[i]),min(flag,a[i]));
}
LL sum=0;
for(LL i=1;i<=n;i++)
{
b[i]=flag/a[i];
sum+=b[i];
}
if(m%sum!=0)
{
printf("No\n");
continue;
}
printf("Yes\n");
LL beishu=m/sum;
for(LL i=1;i<=n;i++)
{
if(i==1)
printf("%lld",b[i]*beishu);
else
printf(" %lld",b[i]*beishu);
}
printf("\n");
}
return 0;
}
I.Budget
思路：这个题卡的是精度，因为是1e18,所以double也存放不下。得用字符串来解决！
#include<bits/stdc++.h>
//#define maxn 1005
//double a[maxn];
//double b[maxn];
using namespace std;
int main(){
int n;
string a;
long double sum =0;
while(cin>>n){
for(int i =0;i<n;i++){
cin>>a;
int len = a.length();
if(a[len-1] >='5'){
sum += 58 - a[len-1];
}
else
sum -= a[len-1]-'0';
}
sum /=1000.0;
cout<<fixed<<setprecision(3)<<sum<<endl;
}
return 0;
}
H.RNG
思路：主要是式子的推导过程，因为正面想比较困难，所以我们可以从反面求他们不相交的概率，及第一个选取的区间的左边界小于第二个选取的区间的右边界。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll pow(ll a, ll n){
ll res = 1;
while(n){
if(n & 1)
res = res * a %mod;
a = a * a %mod;
n >>= 1;
}
return res;
}
int main(){
ll n;
while(cin>>n){
cout<<(n+1)*pow(2*n,mod-2)%mod<<endl;
}
return 0;
}
G.Traffic
思路：首先要理解题意，一开始我就把题的意思搞错了，然后思路搞偏了好远。是东西方向的车不用做变化，要南北方向的车全部都等待相同的时间然后这样进行通过时不相撞。那我们就可以把东西方向的读入的时候记得标记一下，然后就行一个对时间从1到无穷的一个死循环，如果存在一个时间使得所有的南北方向的车在通过时均都不和东西方向的车互撞，那么就输出这个时间，并打破循环即可！
#include<bits/stdc++.h>
#define maxn 3005
int a[maxn],b[maxn];
//int flag[maxn];
int flag;
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;i++){
cin>>flag;
a[flag] = 1;//标记什么时间段有车；
}
for(int i=0;i<m;i++)
cin>>b[i];
for(int i=0;;i++){
int flag1= 0;
for(int j=0;j<m;j++){
if(a[b[j]+i] == 0)
flag1++;
}
if(flag1 == m) {
cout<<i<<endl;
break;
}
}
}
return 0;
}
F.String
思路：水体秒之（伤心，我们GCD的模板敲错了，导致W了好几次）检查半天，还以为思路有问题，结果只是水体一道！
#include<bits/stdc++.h>
#define maxn 105
char a[maxn];
using namespace std;
int gcd(int a,int b){
return b? gcd(b,a%b ):a;
}
int main(){
int n;
//getchar();
while(~scanf("%d",&n)){
for(int i=0;i<n;i++)
cin>>a[i];
int num1=0,num2=0,num3=0,num4=0;
long long int sum;
for(int i =0;i<n;i++){
if(a[i] == 'a')
num1++;
if(a[i] == 'v')
num2++;
if(a[i] == 'i')
num3++;
if(a[i] =='n')
num4++;
}
sum = num1*num2*num3*num4;
long long int sum1 = n*n*n*n;
if(sum == 0) cout<<"0/1"<<endl;
else{
int yue = gcd(sum,sum1);
cout<<sum/yue<<"/"<<sum1/yue<<endl;
}
}
return 0;
}
以上就是我做的几道水体；
A. Cotree
思路：对于每棵树进行换根dp，对每棵子树找到一个点使得所有点到这个点的距离和最小，连接这两个点，然后进行一次DFS统计每条边的贡献，累加即可。（学长写的题解是这样的，nuonuo表示看不懂，对不起，我太弱了！）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
vector<long long> G[N];
int n,n1,n2;
bool vis[N];
long long ans;
void dfs1(int x){
if(vis[x]) return ;
vis[x]=1;
for(auto v:G[x]){
dfs1(v);
}
}
int ta,tb,now;
long long dp[N];long long siz[N];
void dfs2(long long u,long long fa){
siz[u]=1;
for(auto v:G[u]){
if(v==fa) continue;
dfs2(v,u);
siz[u]+=siz[v];
dp[u]+=dp[v];
}
dp[u]+=siz[u];
}
void dfs3(long long u,long long fa){
if(ans>dp[u]){
ans=dp[u];
now=u;
}
for(auto v:G[u]){
if(v==fa) continue;
long long res=dp[u]-dp[v]-siz[v];
dp[v]=(dp[v]+res+n1-siz[v]);
dfs3(v,u);
}
}
void dfs4(long long u,long long fa){
if(ans>dp[u]){
ans=dp[u];
now=u;
}
for(auto v:G[u]){
if(v==fa) continue;
long long res=dp[u]-dp[v]-siz[v];
dp[v]=(dp[v]+res+n2-siz[v]);
dfs4(v,u);
}
}
long long final=0;
void dfs(int now,int fa){
final+=siz[now]*(n-siz[now]);
for(auto v:G[now]){
if(v==fa) continue;
dfs(v,now);
}
}
int main(){
//freopen("1.in","r",stdin);
cin>>n;
int u,v;
for(int i=1;i<=n-2;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
int a,b;//找到左子树的一个点和右子树的一个点
a=1;dfs1(1);
for(int i=2;i<=n;i++){
if(!vis[i]){
b=i;n2++;
}
}
n1=n-n2;
ans=99999999999999;
now=a;
dfs2(a,0);
dfs3(a,0);
ta=now;
memset(dp,0,sizeof(dp));
memset(siz,0,sizeof(siz));
ans=99999999999999;
now=b;
dfs2(b,0);
dfs4(b,0);
tb=now;
G[ta].push_back(tb);
G[tb].push_back(ta);
memset(dp,0,sizeof(dp));
memset(siz,0,sizeof(siz));
dfs2(1,0);
dfs(1,0);
cout<<final<<endl;
return 0;
}
D.Wave
思路：这个题是我最后看的，我感觉是剩下来的里面最简单的了。题目意思也比较容易理解，但是并没有时间去解决他了，而且过的人数也不是特别的多。当时也没什么思路，只是单纯的感觉简单额鹅鹅鹅~~
那么让我们来欣赏一下我们伟大的学长的代码吧~
思路：任意两个数的位置存一下，然后我们进行暴力枚举即可！
#include<bits/stdc++.h>
const int maxn=1e5+5;
typedef long long ll;
using namespace std;
vector<int>vec[105];
int main()
{
int n,c;
cin>>n>>c;
int x;
for(int t=1;t<=n;t++)
{
scanf("%d",&x);
vec[x].push_back(t);
}
int ans=0;
for(int t=1;t<=c;t++)
{
for(int j=1;j<=c;j++)
{
if(t==j)continue;
int s1=vec[t].size();
int s2=vec[j].size();
int st1=0,st2=0;
int temp=0;
int sum=0;
for(;;)
{
while(st1<s1&&vec[t][st1]<temp)
{
st1++;
}
if(st1==s1)
{
break;
}
temp=vec[t][st1];
sum++;
while(st2<s2&&vec[j][st2]<temp)
{
st2++;
}
if(st2==s2)
{
break;
}
sum++;
temp=vec[j][st2];
}
ans=max(ans,sum);
}
}
printf("%d\n",ans);
return 0;
}
京公网安备 11010502036488号