T1
T1 可能 (一定) 在某些大佬的眼中就是一道送分题 (然而我只有 10 分)
明眼人都看得出来这是一道拓展欧几里得的题目, 我们知道系数 \(a,b\), 要求解方程 \(ax+by=c\) 并且使得 \(|x|+|y|\) 取得最小值
我们知道拓展欧几里得可以求解 \(ax+by=gcd(a,b)\), 并且如果有某一正数 c 满足 \(c\)%\(gcd(a,b)==0\), 令 \(k=c/gcd(a,b)\) 那么显然 \(akx+bky=c\) 令 \(x=kx,y=ky\) 我们现在相当于求解 \(|x|+|y|\)
对于一个方程 显然 \(ax+by=gcd(a,b)\) 与 \(a(x-nb)+b(y+na)=x\) 是等价的 因此我们可以将我们用拓展欧几里得求出来的特殊解通过这种变形, 求得满足条件的解. 而如果要满足条件的话, 我们需要让 \(x-nb\) 接近于 0 或者令 \(y+na\) 接近于 0
假设 \(a<b\) 显然如果 x 变化了 那么对于 y 的变化是很小的 因此如果让 a 的未知数 x 接近于 0, 对于 y 的影响是比较小的, 那么可以优化一下, 将问题简化一下 (即在开始的时候 \(if(a<b) swap(a,b)\))
然后就可以做了 (其实不要上面的优化也可以)
- #include
- #include
- #include
- #include
- #include
- #define ll long long
- using namespace std;
- const int maxn=200010;
- ll read(){
- ll 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 exgcd(ll a,ll b,ll &x,ll &y){
- if(a%b==0){
- x=1;y=0;return b;
- }
- ll d=exgcd(b,a%b,x,y),t;
- t=y-a/b*x;
- y=x;
- x=t;
- return d;
- }
- ll n,num[maxn],a,b;
- int main()
- {
- // freopen("array.in","r",stdin);
- // freopen("arrayown.out","w",stdout);
- n=read();a=read();b=read();
- if(a<b) a^=b^=a^=b;
- ll d,x,y,ans=0;
- d=exgcd(a,b,x,y);
- a/=d;b/=d;
- // 这里一定要除哦 不然要 WA
- for(ll i=1;i<=n;i++){
- num[i]=read();
- if(abs(num[i])%d)
- return printf("-1"),0;
- ll X=x*(num[i]/d),Y=y*(num[i]/d);
- swap(X,Y);
- //x 对应的系数大 y 对应的系数小
- // 因为要改变 y 使得 y 尽量为接近零的数
- if(Y<0){// 使得 Y 变正
- X-=b*((-Y)/a+1);
- Y+=a*((-Y)/a+1);
- }
- X+=b*((Y)/a);
- Y-=a*((Y)/a);
- ans=ans+min(abs(X)+abs(Y),abs(X+b)+abs(Y-a));
- }
- printf("%lld",ans);
- }
- T2
咕咕咕
- #include<bits/stdc++.h>
- #define L long long
- #define vi vector
- #define pb push_back
- using namespace std;
- int n,m,w[200010],p;
- L f[800010],g[800010];
- struct orz
- {
- int a,b,p;
- }x[100010];
- inline bool cmp(orz a,orz b)
- {
- return a.a+a.b<b.a+b.b;
- }
- inline void down(int i)
- {
- f[i<<1]+=g[i];
- g[i<<1]+=g[i];
- f[i<<1|1]+=g[i];
- g[i<<1|1]+=g[i];
- g[i]=0;
- }
- inline L query(int i,int j,int k,int p)
- {
- if(j==k)
- return f[i];
- down(i);
- if(p<=j+k>>1)
- return query(i<<1,j,j+k>>1,p);
- else
- return max(f[i<<1],query(i<<1|1,(j+k>>1)+1,k,p));
- }
- inline void maxx(int i,int j,int k,int p,L q)
- {
- f[i]=max(f[i],q);
- if(j!=k)
- {
- down(i);
- if(p<=j+k>>1)
- maxx(i<<1,j,j+k>>1,p,q);
- else
- maxx(i<<1|1,(j+k>>1)+1,k,p,q);
- }
- }
- inline void add(int i,int j,int k,int l,int r,int p)
- {
- if(l<=j && k<=r)
- {
- f[i]+=p;
- g[i]+=p;
- }
- else
- {
- down(i);
- if(l<=(j+k>>1))
- add(i<<1,j,j+k>>1,l,r,p);
- if(r>(j+k>>1))
- add(i<<1|1,(j+k>>1)+1,k,l,r,p);
- f[i]=max(f[i<<1],f[i<<1|1]);
- }
- }
- int main()
- {
- freopen("pair.in","r",stdin);
- freopen("pair.out","w",stdout);
- int i,j;
- L k;
- scanf("%d",&n);
- for(i=1;i<=n;i++)
- {
- scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].p);
- w[++m]=x[i].a;
- w[++m]=x[i].b;
- }
- sort(w+1,w+m+1);
- m=unique(w+1,w+m+1)-w;
- for(i=1;i<=n;i++)
- {
- x[i].a=lower_bound(w+1,w+m,x[i].a)-w;
- x[i].b=lower_bound(w+1,w+m,x[i].b)-w;
- }
- sort(x+1,x+n+1,cmp);
- for(p=1;p<m;p<<=1);
- for(i=1;i<=n;i++)
- {
- j=min(x[i].a,x[i].b);
- k=query(1,1,p,j)+x[i].p;
- maxx(1,1,p,x[i].a,k);
- if(x[i].b>x[i].a)
- add(1,1,p,x[i].a+1,x[i].b,x[i].p);
- }
- printf("%lld\n",f[1]);
- return 0;
- }
- T3
这道题的话呢 在大佬眼中这就是一道板子题 但是蒟蒻调了好久 (原因竟是 m 条边只输入了 n 条)
emmm 首先对于两个特殊点之间距离的转移, 要不就是他们直接连接, 要不就是他们不直接连接, 并且通过其他的点转移过来 (注意, 只有可能由其他不是特殊点的点转移过来, 因为如果是从其他特殊点转移过来, 显然会更劣 因为转移过来的特殊点显然更优)
- #include
- #include
- #include
- #include
- #include
- #define LL long long
- #define int long long
- using namespace std;
- const LL maxn=400010;
- LL read(){
- LL 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;
- }
- struct node
- {
- int dis;
- int pos;
- bool operator <( const node &x )const
- {
- return x.dis <dis;
- }
- };
- priority_queue q;
- LL n,m,p,spe[maxn],tot=1,from[maxn],dis[maxn],ans[maxn<<1];
- LL fir[maxn<<1],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],inque[maxn<<1];
- void add(LL x,LL y,LL z){
- nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;val[tot]=z;
- nxt[++tot]=fir[y];fir[y]=tot;to[tot]=x;val[tot]=z;
- }
- void dij()
- {
- int rp,des;
- for(int i=1;i<=p;i++)
- q.push(node{0,spe[i]});
- while(!q.empty())
- {
- node tmp=q.top();
- q.pop();
- int x=tmp.pos;int y=tmp.dis;
- if(inque[x]) continue;
- inque[x]=true;
- for(rp=fir[x];rp;rp=nxt[rp])
- {
- des=to[rp];
- if(dis[des]>y+val[rp]){
- dis[des]=y+val[rp];
- from[des]=from[x];
- if(inque[des]==false)
- {
- q.push( ( node ){dis[des], des} );
- }
- }
- }
- }
- }
- signed main(){
- // freopen("distance.in","r",stdin);
- // freopen("distanceown.out","w",stdout);
- n=read();m=read();p=read();
- for(LL i=1;i<=p;i++)
- spe[i]=read();
- for(LL i=1,x,y,z;i<=m;i++){
- x=read();y=read();z=read();
- add(x,y,z);
- }
- for(LL i=1;i<=n;i++)
- dis[i]=1e18,ans[i]=1e18;
- for(LL i=1;i<=p;i++)
- dis[spe[i]]=0,from[spe[i]]=spe[i];
- dij();
- for(LL x=1;x<=n;x++){
- for(LL i=fir[x];i;i=nxt[i]){
- LL y=to[i];
- if(from[x]!=from[y])
- ans[from[x]]=min(ans[from[x]],dis[x]+dis[y]+val[i]);
- }
- }
- for(LL i=1;i<=p;i++)
- {
- if(i!=p)
- printf("%lld",ans[spe[i]]);
- else printf("%lld\n",ans[spe[i]]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3263971.html