题解报告
基本的一些理解和问题都在注释中
A：Filter
//水题
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main(void)
{
int N;cin>>N;
for(int i=0;i<N;i++)
{
int x;cin>>x;
if(!(x&1))cout<<x<<' ';
}
cout<<endl;
return 0;
}
//水题，但是错了一发，可惜可惜，注意输出格式。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000;
char ans[maxn][maxn];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int N,M;cin>>N>>M;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
int x;cin>>x;
if(x==0)ans[i][j]='.';
else ans[i][j]=x-1+'A';
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
cout<<ans[i][j];//注意输出的规格，这里没有空格
cout<<endl;
}
return 0;
}
//水题
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;
const int maxn=1e6+10;
unordered_map<int,int> mp;
int num1[maxn];
int num2[maxn];
struct node
{
int x;
bool operator <(const node &a)const
{
return x<a.x;
}
}res[maxn];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int N,M;cin>>N>>M;
int pos=0;
for(int i=1;i<=N;i++)cin>>num1[i],res[pos++].x=num1[i];
for(int j=1;j<=M;j++)cin>>num2[j],res[pos++].x=num2[j];
sort(res,res+pos);
for(int i=0;i<pos;i++)mp[res[i].x]=i+1;
for(int i=1;i<=N;i++)cout<<mp[num1[i]]<<' ';cout<<endl;
for(int i=1;i<=M;i++)cout<<mp[num2[i]]<<' ';
return 0;
}
D：Bank
//优先队列模拟，读懂题目就容易写
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=5e5+10;
int vis[maxn];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
priority_queue<int,vector<int>,greater<int> >q1;
int Q,N;cin>>N>>Q;
int Cpos=0;
for(int i=1;i<=Q;i++)
{
int op;cin>>op;
if(op==1){
if(Cpos<N)
q1.push(++Cpos);
}else if(op==2){
int k;cin>>k;
vis[k]=1;
}else{
while(!q1.empty()&&vis[q1.top()])q1.pop();
cout<<q1.top()<<endl;
}
}
return 0;
}
E：2xN Grid
//模拟题，上下两边同时推进。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn=1e5+10;
struct node
{
long long v,l;
};
node num1[maxn];
node num2[maxn];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
long long L;cin>>L;
int N1,N2;
cin>>N1>>N2;
for(int i=1;i<=N1;i++)cin>>num1[i].v>>num1[i].l;
for(int j=1;j<=N2;j++)cin>>num2[j].v>>num2[j].l;
long long i=0,j=0;
int pos1=1,pos2=1;
long long res=0;
while(i!=L&&j!=L&&pos1<=N1&&pos2<=N2)
{
if(num1[pos1].l+i>num2[pos2].l+j)//更新左边
{
if(num1[pos1].v==num2[pos2].v)
res+=num2[pos2].l+j-max(i,j);
j+=num2[pos2].l;pos2++;
num1[pos1].l=num1[pos1].l+i-j;
i=j;
}else{
if(num1[pos1].v==num2[pos2].v)
res+=num1[pos1].l+i-max(i,j);
i+=num1[pos1].l;pos1++;
num2[pos2].l=num2[pos2].l+j-i;
j=i;
}
}
cout<<res<<endl;
return 0;
}
//一道二分的题目，虽然刚开始我也是想二分，二分的也是浓度，但是写check函数的时候就写出问题了
//chek函数要根据每个的贡献来的，不能盲目枚举，以后要是有分数的，都直接看贡献。
//这道题上周在周赛的时候有做过类似的，做不出来不应该的。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=5e4+10;
double A[maxn],B[maxn];
double C[maxn],D[maxn];
double temp[maxn];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int N,M;cin>>N>>M;
long long K;cin>>K;
for(int i=1;i<=N;i++)cin>>A[i]>>B[i];
for(int i=1;i<=M;i++)cin>>C[i]>>D[i];
double l=0,r=1;
while(abs(r-l)>=1e-15)
{
double mid=(l+r)/2;
double k=mid/(1-mid);
for(int i=1;i<=N;i++)temp[i]=A[i]-B[i]*k;//看提供的糖是多了还是少了
sort(temp+1,temp+N+1);
long long res=0;
for(int i=1;i<=M;i++)
{
double has=C[i]-D[i]*k;
res+=N-(lower_bound(temp+1,temp+1+N,-has)-(temp+1));
//获取的浓度大于等于它的个数。
//这里是大于等于它的，可能全部都是大于的，所以就算，等于了，
//那么也还是得提高浓度，找到一个存在的且真正是临界点的才行。
}
//个数多了，浓度加大。
if(res>=K)l=mid;//要实实在在的找到里面有的才行，所以
else r=mid;
}
printf("%.16lf",r*100);
return 0;
}
//树链刨分的板子题，只不过是边权的而已，要注意以下就行了。
//会就乱杀，不会就不会写。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=4e5+10;
//建树
int head[maxn],edge[maxn],nxt[maxn],ver[maxn],tot;
ll w[maxn];
//边权化为点权，遍历的时候转换。
int dep[maxn],siz[maxn],hson[maxn],fa[maxn],top[maxn],dfn[maxn],rnk[maxn];
void addEdge(int u,int v,int w)
{
ver[tot]=w;
edge[tot]=v;
nxt[tot]=head[u];
head[u]=tot++;
}
int mp[maxn];
//线段树
struct node
{
int lson,rson;
long long data;
}tree[maxn<<2];
//刨分
void build(int pos,int l,int r)
{
tree[pos].lson=l;tree[pos].rson=r;
if(l==r)
{
tree[pos].data=w[rnk[l]];
return;
}
int mid=l+r>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
tree[pos].data=tree[pos<<1].data+tree[pos<<1|1].data;
}
ll query(int pos,int l,int r)
{
if(l<=tree[pos].lson&&tree[pos].rson<=r)return tree[pos].data;
int mid=tree[pos].lson+tree[pos].rson>>1;
ll ans=0;
if(l<=mid)
ans+=query(pos<<1,l,r);
if(r>=mid+1)
ans+=query(pos<<1|1,l,r);
return ans;
}
void update(int pos,int x,int val)
{
if(tree[pos].lson==tree[pos].rson)
{
tree[pos].data=val;
return;
}
int mid=tree[pos].lson+tree[pos].rson>>1;
if(x<=mid)
update(pos<<1,x,val);
else
update(pos<<1|1,x,val);
tree[pos].data=tree[pos<<1].data+tree[pos<<1|1].data;
}
void dfs1(int now,int pre,int step)
{
siz[now]=1;
hson[now]=-1;
dep[now]=step;
fa[now]=pre;
for(int i=head[now];~i;i=nxt[i])
{
int v=edge[i];
if(v==pre)continue;
mp[i/2*2]=v;
w[v]=ver[i];
dfs1(v,now,step+1);
siz[now]+=siz[v];
if(hson[now]==-1||siz[hson[now]]<siz[v])
hson[now]=v;
}
}
int tp=0;
void dfs2(int now,int t)
{
top[now]=t;
tp++;
dfn[now]=tp;
rnk[tp]=now;
if(hson[now]==-1)return;
dfs2(hson[now],t);
for(int i=head[now];~i;i=nxt[i])
{
int v=edge[i];
if(v==hson[now]||v==fa[now])continue;
dfs2(v,v);
}
}
void init(int N,int rt=1)
{
tp=0;
dfs1(rt,rt,1);
dfs2(rt,rt);
build(1,1,N);
}
ll solve(int a,int b)
{
ll ans=0;
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
ans+=query(1,dfn[top[a]],dfn[a]);
a=fa[top[a]];
}
if(dep[a]>dep[b])swap(a,b);
if(a!=b)
ans+=query(1,dfn[a]+1,dfn[b]);
return ans;
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(head,-1,sizeof(head));
int N;cin>>N;
for(int i=0;i<N-1;i++)
{
int u,v,w;cin>>u>>v>>w;
addEdge(u,v,w);
addEdge(v,u,w);
}
init(N,1);
int Q;cin>>Q;
for(int i=0;i<Q;i++)
{
int op,x,y;
cin>>op>>x>>y;
if(op==1){
update(1,dfn[mp[(x-1)*2]],y);//改的位置不一样。
}else{
cout<<solve(x,y)<<endl;
}
}
return 0;
}
这次的还算比较简单的，但是我的排名却不咋地，继续努力吧。
- Beginner AtCoder Contest 294beginner atcoder contest 294 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327