A - Red Or Not
水题:n>=3200 输出 s,否则输出red
//#include<bits/stdc++.h>
#define ll long long
#include <stdio.h>
#include <algorithm>
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e6+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m,x;
char str[100005];
int main()
{
scanf("%lld%s",&n,str);
if(n>=3200) printf("%s\n",str);
else printf("red\n");
return 0;
} B - Resistors in Parallel
水题:题目给出 a1,a2,a3,ai , 输出 1/(1/a1+1/a2+.....1/ai),为了确保精度,首先将其通分化为一个分数,之后用double输出.
//#include<bits/stdc++.h>
#define ll long long
#include <stdio.h>
#include <algorithm>
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e6+1000;
const int INF=1e9+7;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m;
ll num[maxn];
ll gcd(ll a,ll b)
{
if(!b) return a;
return gcd(b,a%b);
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
ll lcm=num[1];
for(int i=2;i<=n;i++)
{
ll temp=gcd(lcm,num[i]);
lcm=lcm*num[i]/temp;
}
ll sum=0;
for(int i=1;i<=n;i++)
sum+=lcm/num[i];
// printf("%lld %lld\n",sum,lcm);
double res=(double)(lcm)*1.0;
double res1=(double)(sum)*1.0;
printf("%.6lf\n",res/res1*1.0);
return 0;
} C - Alchemist
题目大意:给你n个数,你每次可以合并两个数,使这两个数变成(a+b)/2 ,然后再放回原数组,一直这么重复,最后数组将剩下一个数,问最后这个数的最大值是多少.
题目思路:贪心问题,因为每次合并,都会使每个数的贡献/2,那么就应该让小的先合并,大的合并次数越少,对结果贡献就越大
可以每次排序,因为n才50,也可以优先队列
AC(优先队列):
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
struct node{
double w;
}num[150];
bool operator<(node a,node b)
{
return a.w>b.w;
}
int main()
{
priority_queue<node>q;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lf",&num[i].w);
q.push(num[i]);
}
while(q.size()!=1)
{
node u=q.top();q.pop();
node u1=q.top();q.pop();
node now;now.w=(u.w+u1.w)*0.5;
q.push(now);
}
printf("%.7lf\n",q.top().w);
return 0;
} D - Ki
题目大意:给你n个点,n-1条边,构成一颗树,这棵树以1为根节点,随后m行,每行 pi ,ai,表示以pi为根节点的子树的权值都加ai(包括pi),问最后每一个节点的权值是多少.
题目思路:我们把树遍历一遍就可以了,先预处理每个节点加了多少,经过这个节点后,sum+=当前节点权值,每次都更新当前节点权值.因为这是一棵树 复杂度O(N-1)
AC:
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
struct node{
int e,next;
}edge[maxn];
int head[maxn];
ll cot[maxn];
ll res[maxn];
ll cnt=0;
void addedge(int u,int v)
{
edge[cnt]=node{v,head[u]};
head[u]=cnt++;
edge[cnt]=node{u,head[v]};
head[v]=cnt++;
}
void dfs(int u,int fa,ll sum)
{
res[u]=sum;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int e=edge[i].e;
if(e!=fa)
dfs(e,u,sum+cot[e]);
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
}
for(int i=1;i<=m;i++)
{
ll x,y;
scanf("%lld%lld",&x,&y);
cot[x]+=y;
}
addedge(0,1);
dfs(0,-1,0);
for(int i=1;i<=n;i++)
printf("%lld ",res[i]);
return 0;
} F - String of Impurity
题目大意:给你两个字符串s,t,其中s可以复制为 s1,s2,s3,s4....sn,问当t是s复制的字符串的子序列时最小的长度
例子:s=contest t=son s2=contestcontest 当s复制两次时,t是s2的子序列并且最小长度为 contestcon =10
题目思路:如果同时n^2遍历两个字符串绝对会超时,我们就遍历一个字符串,我们遍历t,这时候需要一个东西辅助 ---- 序列自动机.我们用序列自动机存下s当前位置的下一个t的字符在哪,如果找不到那就需要复制一遍s,这时位置=t当前字符在s中第一次出现的位置,所以 预处理 t中字母在s中第一次出现的位置,无解条件,t中出现的字母s中没有出现
AC:
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
bool viss[30];
char s[100005],t[100005];
int nex[100005][30];
int loca[30];// 标记初始位置
void restart(int len)
{
for(int i=1;i<=len+1;i++)
for(int k=1;k<=26;k++)
nex[i][k]=-1;
for(int i=len;i>=2;i--)
{
for(int k=1;k<=26;k++) nex[i-1][k]=nex[i][k];
nex[i-1][s[i]-'a'+1]=i;
}
}
int main()
{
bool f=false;
scanf("%s%s",s+1,t+1);
int lens=strlen(s+1),lent=strlen(t+1);
restart(lens);
for(int i=1;i<=lens;i++)
{
if(!viss[s[i]-'a'+1])
{
loca[s[i]-'a'+1]=i;
viss[s[i]-'a'+1]=true;
}
}
for(int i=1;i<=lent;i++)
if(viss[t[i]-'a'+1]==false)
{
f=true;
break;
}
if(f) printf("-1\n");
else
{
ll ans=0;// 次数与最后长度
ll st=loca[t[1]-'a'+1],peace=1;;
while(peace!=lent)
{
ll temp=t[peace+1]-'a'+1;
if(nex[st][temp]!=-1)
st=nex[st][temp];
else
{
st=loca[temp];
ans++;
}
peace++;
}
printf("%lld\n",ans*lens+st);
}
return 0;
} F - Coincidence
还没做出来.....
总结:
昨天回去累了,下午5点睡觉到9.10.....起来之后 还剩半个小时结束比赛. 疯狂掉分ing...上午抽空补了一下发现不应该掉分的们这次比赛还是能做的,唉,不管怎么样掉了分就继续上,加油了ACMer
京公网安备 11010502036488号