永久网站域名,制作动漫的软件,网页升级紧急通知 直接跳转中,怎么样才能让百度收录自己的网站T1.fuction 吐槽一波错误拼写。 跟考场思路差不多#xff0c;只不过细节挺多的呢。 判掉a0,b0,c0的几种组合#xff0c;还有负数的情况要打标记特殊处理。 然后就是一个拓欧啦#xff0c;先求出ggcd(a,b)#xff0c;顺便求出axbyg的x和y#xff0c;然后根据裴蜀定理#…T1.fuction 吐槽一波错误拼写。 跟考场思路差不多只不过细节挺多的呢。 判掉a0,b0,c0的几种组合还有负数的情况要打标记特殊处理。 然后就是一个拓欧啦先求出ggcd(a,b)顺便求出axbyg的x和y然后根据裴蜀定理或者是直觉我们知道axby可以以g为长度遍历数轴要是c%g!0那就无解了。 然后是可以整除的情况就把x和y乘以dc/g这样就求出了axbyc的一组x和y了定x为较小的数把x补到正同时y跟着减要是x刚好到正y已经负了那就是无解。 还有此时如果a和b是一正一负的是无穷多解的因为可以正负系数同时不断扩大。 然后剩下的情况就是x和y都是正整数啦此时为了满足axbyc考虑有多少种等价情况也就是x加上一个sa*xy就得减去一个sb*y显然salcm(a,b)/ab/g同理sba/g 因为x是增大的y是减小的我们只需要判断y能减多少个sb就可以啦。 #includeiostream
#includecstdio
#define NON puts(0),0
#define INF puts(ZenMeZheMeDuo),0
using namespace std;const int MAX65535;inline int rd(){int ret0,f1;char c;while(cgetchar(),!isdigit(c))fc-?-1:1;while(isdigit(c))retret*10c-0,cgetchar();return ret*f;
}typedef long long ll;ll exgcd(ll A,ll B,ll x,ll y){if(!B) return x1,y0,A;ll retexgcd(B,A%B,y,x);y-A/B*x;return ret;
}ll T,a,b,c;int solve(){ard();brd();crd();bool fa0,fb0;if(a0b0) a-a,b-b,c-c;if(!a)if(c%b0c/b0) return INF;else return NON;if(!b)if(c%a0c/a0)return INF;else return NON;if(a0b0)return c?NON:INF;if(a1b1)return cMAX-1?INF:printf(%lld\n,c-1);if(a0) fa1,a-a;if(b0) fb1,b-b;if(abc)return puts(1),0;ll x,y;ll gexgcd(a,b,x,y);if(c%g) return NON;ll dc/g;x*d;y*d;if(fa) a-a,x-x;if(fb) b-b,y-y;ll sab/g,sba/g;if(a*b0) return INF;ll tx/sa-1;if(x%sa0) t--;x-t*sa;yt*sb;if(xsa) x-sa,ysb;if(y0) return NON;ll ansy/sb(y%sb!0);if(ansMAX) return INF;printf(%lld\n,ans);return 0;
}int main(){Trd();while(T--) solve();return 0;
} View Code T2.coloration 树形DP提供了一种好的思路。 涉及考虑树上点对的题与其O(n^2)地考虑任意两点的关系不如考虑每条边的贡献。 本题中对于一条边e它的边权为w其贡献为 (左侧黑点*右侧黑点左侧白点*右侧白点)*w 设f[i][j]为以i为根的子树中选取j个黑点的最大贡献转移时逐个合并子树用一个g数组先跑一次背包再添加进f状态。 复杂度O(n^2)卡好边界。 注意int到long long要乘一个1ll #includeiostream
#includecstring
#includecstdiousing namespace std;const int MAXN2048;inline int rd() {int ret0,f1;char c;while(cgetchar(),!isdigit(c))fc-?-1:1;while(isdigit(c))retret*10c-0,cgetchar();return ret*f;
}struct Edge {int next,to,w;
} e[MAXN1];
int ecnt,head[MAXN];
inline void add(int x,int y,int w) {e[ecnt].to y;e[ecnt].next head[x];e[ecnt].w w;head[x] ecnt;
}int n,m;
long long f[MAXN][MAXN],g[MAXN];
int siz[MAXN];
int dfs(int x,int pre) {siz[x]1;for(int ihead[x]; i; ie[i].next) {int ve[i].to;if(vpre) continue;memset(g,0,sizeof(g));dfs(v,x);for(int jmin(m,siz[x]); j0; j--)for(int kmin(m-j,siz[v]); k0; k--)g[jk]max(g[jk],f[x][j]f[v][k]((k*(m-k)(siz[v]-k)*(n-m-siz[v]k))*1ll*e[i].w));for(int j0; jm; j)f[x][j]g[j];siz[x]siz[v];}
}int main() {nrd();mrd();int x,y,w;for(int i1; in-1; i) {xrd();yrd();wrd();add(x,y,w);add(y,x,w);}dfs(1,0);coutf[1][m];
} View Code T3.ray 神题正解居然是模拟。 考场写了四类分类讨论预期得分60实际扣了一些可能是写挂了一部分的原因。 考场想到了离散化存储二分查找但是突然觉得这样会多一个log感觉最差情况的状态数是n^2的非常不可做就用一个二维数组直接存了。 事实上是可以离散化存的这样就有70分啦。实际复杂度确实是O(nmlogn) #includealgorithm
#includeiostream
#includestring
#includecstdio
#includevectorusing namespace std;const int MAXN100005;inline int rd(){int ret0,f1;char c;while(cgetchar(),!isdigit(c))fc-?-1:1;while(isdigit(c))retret*10c-0,cgetchar();return ret*f;
}vectorint V[MAXN];bool vis[MAXN];
inline bool vaild(int x,int y){return !binary_search(V[x].begin(),V[x].end(),y);}
inline void add(int x,int y){vis[x]1;V[x].push_back(y);} int n,m,lim,stx,sty,stdir;const int dx[5]{0,-1,-1,1,1};
const int dy[5]{0,1,-1,1,-1};int main(){nrd();mrd();limrd();int x,y;for(int i1;ilim;i){xrd();yrd();add(x,y);}for(int i0;in1;i){add(i,0);add(i,m1);}for(int i0;im1;i){add(0,i);add(n1,i);}stxrd();styrd();string s;cins;if(sNE) stdir1;if(sNW) stdir2;if(sSE) stdir3;if(sSW) stdir4;for(int i1;i100000;i) if(vis[i]) sort(V[i].begin(),V[i].end());//nlogn is better :)int cur,nx,ny,t1,t2;long long cnt0;xstx;ysty;curstdir;bool db0;while(cnt0||x!stx||y!sty||cur!stdir){nxxdx[cur];nyydy[cur];cnt;if(vaild(nx,ny)){xnx;yny;continue;}switch(cur){case 1:{t1vaild(nx,ny-1);t2vaild(nx1,ny);if(!(t1^t2)){db1;cur4;continue;}if(!t1){y;cur3;continue;}if(!t2){x--;cur2;continue;}break;}case 2:{t1vaild(nx1,ny);t2vaild(nx,ny1);if(!(t1^t2)){db1;cur3;continue;}if(!t1){x--;cur1;continue;}if(!t2){y--;cur4;continue;}break;}case 3:{t1vaild(nx,ny-1);t2vaild(nx-1,ny);if(!(t1^t2)){db1;cur2;continue;}if(!t1){y;cur1;continue;}if(!t2){x;cur4;continue;}break;}case 4:{t1vaild(nx-1,ny);t2vaild(nx,ny1);if(!(t1^t2)){db1;cur1;continue;}if(!t1){x;cur3;continue;}if(!t2){y--;cur2;continue;}break;}}}if(db) cnt1;coutcntendl;return 0;
} 70pts 正解是这样的我们不去考虑每一步怎么走而是考虑沿着这个方向可以到达哪里哪个反射点。 反射点的位置是可以计算的可以证明反射的次数是O(nmk)级别的再加上关于k个限制的二分总复杂度在O((nmk)logk)可以接受 对于先后经过的两个反射点u,v它们一定处于一个正方形对角线上所以其距离就是切比雪夫距离。 所以现在就要快速地找到某条对角线上下次出现的点了怎么做呢 对于左上到右下对角线上的点(x,y)x-y是一个定值与在第几条有关。 同理对于右上到左下的xy是一个定值可以唯一代表第几条对角线。 因此我们重新将坐标分别写为(xy,x),(x-y,x)这即保留了原始的坐标信息可以O(1)算出还可以通过把第一维作为第一关键字使得排序后一条对角线在一个连续区间第二维递增。 这样就可以迅速二分出下一个障碍物啦很快地就可以算出了。 顺便学到了切比雪夫距离好像有人讲过诶忘记了..可以方便地把坐标系旋转45°并放缩sqrt(2)倍。 #includealgorithm
#includeiostream
#includecstdio
#includevector
using namespace std;inline int rd() {int ret0,f1;char c;while(cgetchar(),!isdigit(c))fc-?-1:1;while(isdigit(c))retret*10c-0,cgetchar();return ret*f;
}// CBSV Chebyshev :)
struct CBSV {int fi,se;CBSV(int X,int Y) {fiX;seY;}bool operator(const CBSV rhs) const {return rhs.fifi?serhs.se:firhs.fi;}
};int n,m,lim;
long long ans;
int sx,sy,sdx,sdy;
int cur,dir,dx,dy,db0;vectorCBSV V[2];
vectorCBSV::iterator it;inline void add(int x,int y) {V[0].push_back(CBSV(x-y,x));V[1].push_back(CBSV(xy,x));
}void work(int x,int y) {dir(dx!dy);CBSV nowdir?CBSV(xy,x):CBSV(x-y,x);itupper_bound(V[dir].begin(),V[dir].end(),now);while(it-fi!now.fi) it--;if(dx0) while(it-sex) it--;ansabs(x-it-se)-1;xit-se;ydir?it-fi-x:x-it-fi;int ubinary_search(V[0].begin(),V[0].end(),CBSV(x-y-dx,x-dx));int vbinary_search(V[0].begin(),V[0].end(),CBSV(x-ydy,x));if(uv )db1,dx*-1,dy*-1;else if(u) x-dx,dy*-1;else if(v) y-dy,dx*-1;
}int main() {nrd();mrd();limrd();int x,y;for(int i1; ilim; i) {xrd();yrd();add(x,y);}for(int i0; in1; i) add(i,0),add(i,m1);for(int i0; im1; i) add(0,i),add(n1,i);sort(V[0].begin(),V[0].end());sort(V[1].begin(),V[1].end());char s[50];xrd();yrd();scanf(%s,s);dxs[0]N?-1:1;dys[1]W?-1:1;work(x,y);ans0;sxx;syy;sdxdx;sdydy;do work(x,y);while(!(xsxysydxsdxdysdy));printf(%lld,db?(ans1):ans);
} View Code 转载于:https://www.cnblogs.com/ghostcai/p/9314178.html
