10-6まとめ
5144 ワード
<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">T1: , 30 sb </span>
そして怒って書いて転々としてTを30点落としました...
実は減算をAに変えて70
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<iostream>
int main()
{
long long a,b,ans=-1;
std::cin>>a>>b;
if(a==b)ans++;
while(a!=b)
{
if(b>a)a^=b^=a^=b;
if(b==0)break;
ans+=a/b;a%=b;
}
std::cout<<ans+1<<std::endl;
}
T 2:次小生成木翻版じゃないか、秒の982点はどうやって引いたのか聞かないでください.私は知りません.特判
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
inline void R(int &v)
{
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
struct Edge
{
int to,from,next,len;
}e[2000010],edge[2000010];
int jump[1000010][18];
int first[1000010],f[1000010],s,size;
void add(int x,int y,int z)
{
s++;
e[s].to=y;
e[s].next=f[x];
e[s].from=x;
f[x]=s;
e[s].len=z;
}
void addedge(int x,int y,int z)
{
size++;
edge[size].to=y;
edge[size].len=z;
edge[size].next=first[x];
first[x]=size;
}
bool comp(const Edge &x,const Edge &y)
{
return x.len<y.len;
}
int n,m,k;
int father[100010];
int maxlen[100010][18];
int deep[100010];
int getfather(int v)
{
if(father[v]==v)return v;
father[v]=getfather(father[v]);
return father[v];
}
void dfs(int fa,int now,int len,int dep)
{
jump[now][0]=fa;
maxlen[now][0]=len;
deep[now]=dep;
for(int i=1;i<=17;i++)
{
jump[now][i]=jump[jump[now][i-1]][i-1];
maxlen[now][i]=max(maxlen[now][i-1],maxlen[jump[now][i-1]][i-1]);
}
for(int u=first[now];u;u=edge[u].next)
{
if(edge[u].to!=jump[now][0])
dfs(now,edge[u].to,edge[u].len,dep+1);
}
}
pair<int,int> swam(int x,int len)
{
int maxx=0;
for(int i=17;i>=0;i--)
{
if((1<<i)<=len)
{
len-=(1<<i);
maxx=max(maxx,maxlen[x][i]);
x=jump[x][i];
}
}
return make_pair(x,maxx);
}
pair<int,int> lca(int x,int y)
{
int maxx=0;
if(deep[x]<deep[y])swap(x,y);
if(deep[x]>deep[y])
{
pair<int,int> r=swam(x,deep[x]-deep[y]);
x=r.first;
maxx=r.second;
}
if(x==y)return make_pair(x,maxx);
for(int i=17;i>=0;i--)
{
if(jump[x][i]!=jump[y][i])
{
maxx=max(maxx,maxlen[x][i]);
maxx=max(maxx,maxlen[y][i]);
x=jump[x][i];
y=jump[y][i];
}
}
return make_pair(jump[x][0],maxx);
}
ll ans,ret,sum;
int main()
{
freopen("mst.in","r",stdin);
freopen("mst.out","w",stdout);
R(n),R(m),R(k);
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++)
{
int a,b,c;
R(a),R(b),R(c);
add(a,b,c);
}
sort(e+1,e+s+1,comp);
for(int i=1;i<=s;i++)
{
int x=getfather(e[i].to);
int y=getfather(e[i].from);
if(x!=y)
{
father[x]=y;
addedge(e[i].to,e[i].from,e[i].len);
addedge(e[i].from,e[i].to,e[i].len);
sum+=(ll)e[i].len;
ret=max((ll)((e[i].len<<1)-k),ret);
}
}
ans=sum;
if(ret>0)ans-=ret;
dfs(0,1,0,1);
for(int i=1;i<=s;i++)
{
pair<int,int> r=lca(e[i].to,e[i].from);
//fprintf(stderr,"from %d to %d ,len=%d,maxlen=%d
",e[i].from,e[i].to,min(e[i].len,k-e[i].len),r.second);
int w=min(e[i].len,k-e[i].len);
if(w<r.second)
{
ans=min(ans,(ll)sum+(ll)w-(ll)r.second);
}
}
//cout<<sum<<endl;
//for(int i=1;i<=n;i++)cout<<jump[i][0]<<" "<<maxlen[i][0]<<" "<<maxlen[i][1]<<endl;
cout<<ans<<endl;
}
T3 exgcd裸題秒の100
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mod 1998585857ll
#define ll long long
using namespace std;
inline void R(ll &v)
{
v=0;char c=0;ll p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
ll n;
ll ya[5005];
ll yb[5005];
ll yc[5005];
ll x,y;
ll s;
ll exgcd(ll a,ll b)
{
if(b==0)
{
yb[s]=1;y=0;return a;
}
else
{
ll r=exgcd(b,a%b),z=yb[s];
yb[s]=y;y=z-(a/b)*y;
return r;
}
}
inline void recalc(ll i)
{
ll ret=0;
for(int j=1;j<=i-1;j++)ret=(ret+yc[i-j+1]*yb[j])%mod;
ya[i]=(ya[i]+mod-ret)%mod;
s=(ll)i;y=0;
}
int main()
{
freopen("deconvolution.in","r",stdin);
freopen("deconvolution.out","w",stdout);
R(n);
for(int i=1;i<=n;i++)R(ya[i]);
for(int i=1;i<=n;i++)R(yc[i]);
for(int i=1;i<=n;i++)
{
recalc((ll)i);
ll ans=exgcd(yc[1],mod);
ll t=mod/ans;
ll c=ya[i];
yb[i]=yb[i]*(c/ans);
yb[i]=((yb[i]%t)+t)%t;
}
for(int i=1;i<=n;i++)
{
printf("%d ",yb[i]);
}
}