提交的源程序文件名
对于 C++语言guide.cppfragment.cppfantasy.cpp对于 C 语言guide.cfragment.cfantasy.c对于 Pascal 语言guide.pasfragment.pasfantasy.pas编译选项
对于 C++语言-O2 –lm-O2 –lm-O2 –lm对于 C 语言-O2 –lm -O2 –lm-O2 –lm对于 Pascal 语言-O2-O2-O2Wake up, dead boy, enter adventureland. Tricksters, magicians will show you all that’s real.
N 名迷途的旅者需要小 X 的指引。 初始时， 每一名旅者 i 位于坐标(Ai,Bi)处， 旅者们只能够向右或是向上移动， 也就是说， 他们只能够增加自己的某一维坐标， 而不能减小它们。 这片大地上同样存在者 N 个出口， 每一个出口 i 位于坐标(Ci,Di)处， 一个出 口一旦被某个旅者通过， 它们就会一并消失。 请帮助小 X 计算他至多能够指引多少旅者离开这片大地。
从文件 guide.in 中读取数据。 第一行一个整数 Num， 表示测试点编号， 以便选手方便地获得部分分， 你可 能不需要用到这则信息， 样例中 Num 的含义为数据范围与某个测试点相同。 接下来一行一个整数 N， 含义见题目描述。 接下来 N 行， 每行两个整数 Ai、 Bi， 表示每一名旅者的坐标。 接下来 N 行， 每行两个整数 Ci、 Di， 表示每一个出口的坐标。
一行一个整数， 表示答案。
让位于(2,0)的旅者走到(4,2)处， 让位于(3,1)的旅者走到(5,5)处。
见下发文件 guide2.in， guide2.ans
见下发文件 guide3.in， guide3.ans
见下发文件 guide4.in， guide4.ans
见下发文件 guide5.in， guide5.ans
对于所有测试数据， 保证 1≤N≤105， 0≤Ai、 Bi、 Ci、 Di<2N。 保证 A1,A2,…,AN,C1,C2,…,CN 两两不同。 保证 B1,B2,…,BN,D1,D2,…,DN 两两不同。 特殊性质 1： 保证 Ai=Bi。 特殊性质 2： 保证 Ci=Di。
每个旅者可以选的出口就是从他自己的坐标到右上边界的一个矩形。
同时考虑x,y坐标很难下手。我们将旅者和出口的坐标按x坐标排序。
然后从大到小枚举，每个旅者匹配比其y坐标大的第一个出口（y坐标更大的出口可能匹配上一个y坐标大的旅者)，可以使用线段树维护。
In the ocean, deep down, Under raging waves, wrapped in memories, You’ll find wrecks of stately ships, They all went astray.
小 X 的记忆中， 有一幅 N * M 的中心对称的图案。 而现在， 他的脑海中只有一幅有所变动的图案， 它同样是 N * M 的， 但却不 一定是中心对称的。 小 X 决定修补这一图案， 他能够进行的操作共有两种： 交换两行， 或者交换 两列。 小 X 想要知道能否通过有限（可能为 0） 次操作让它变得中心对称。 为了保证数据的强度， 一个测试点中可能包含多组测试数据。
从文件 fragment.in 中读取数据。 第一行两个整数 Num、 T， Num 表示测试点编号， 以便选手方便地获得部分 分， 你可能不需要用到这则信息， 样例中 Num 的含义为数据范围与某个测试点 相同； T 表示该测试点中包含的测试数据的组数。 对于接下来每一组测试数据， 第一行两个整数 N、 M， 表示图案的大小。 接下来一个 N 行 M 列的字符矩阵， 表示图案。
输出 T 行， 每行一个 YES 或 NO， 表示是否能够使图案中心对称。
交换第 2 列和第 3 列， 得到以下图案： ACB BCA 它是中心对称的。
见下发文件 fragment2.in, fragment2.ans
见下发文件 fragment3.in, fragment3.ans
对于所有测试数据， 保证 1≤N、 M≤12， 1≤T≤10， 图案由大写字母组成。 特殊限制： 图案仅由 A 和 B 组成。
这些行和列的位置并不重要，只需要考虑相对应的行和列使得合法即可，那么暴力选择第一个未被选择的行，再去找一个匹配，时间复杂度 O ( ( 12 ! / 6 ! / 2 6 ) 2 t ) = O ( 1 0 8 t ) O((12!/6!/2^6)^2 t) = O(10^8t) O((12!/6!/26)2t)=O(108t) （然后如果是奇数行或奇数列，需要枚举某一行/列在最中间）
考虑剪枝，很明显两行/列要匹配至少每一种字母个数要相同，因此可以预处理出可以匹配的两个行/列（可能也不需要剪枝），然后再匹配一组后判断当前能否合法。
A nightingale in a golden cage, That’s me locked inside reality’s maze. Come someone make my heavy heart light, Come undone, bring me back to life ?
N 名旅者背井离乡， 前往他乡寻梦。 初始时， 旅者 i 位于自己的家乡 i 号城市。 每一天， 位于 i 号城市的所有旅者都会前往 Ai 号城市， 其中 Ai 是一个在整 个过程中保持不变的量， 由于旅者迫切的寻梦欲望， 我们规定 Ai≠ i。 现在小 X 想要知道， 是否存在至少一组满足条件的 Ai， 使得在 K 天后， 所有 旅者会同时重新回到家乡（在这过程中旅者们同样可以途径自己的家乡） 。 为了保证数据的强度， 一个测试点中可能包含多组测试数据。
从文件 fantasy.in 中读取数据。 第一行两个整数 Num、 T， Num 表示测试点编号， 以便选手方便地获得部分 分， 你可能不需要用到这则信息， 样例中 Num 的含义为数据范围与某个测试点 相同； T 表示该测试点中包含的测试数据的组数。 接下来 T 行， 每一行两个整数 N、 K， 描述每一组数据。
输出 T 行， 每行一个 YES 或 NO， 表示是否存在至少一组满足条件的 Ai。
对于第一组测试数据， 可以令 A={2,3,4,5,6,7,1}。 对于第二组测试数据， 可以证明不存在符合条件的 A。 对于第三组测试数据， 可以令 A={3,4,1,5,2}。
见下发文件 fantasy2.in, fantasy2.ans
见下发文件 fantasy3.in, fantasy3.ans
见下发文件 fantasy4.in, fantasy4.ans
见下发文件 fantasy5.in, fantasy5.ans
对于所有测试数据， 保证 1 ≤ T ≤ 1 0 4 ， 1 ≤ N ≤ 1 0 18 ， 1 ≤ K ≤ 1 0 1 5 1≤T≤10^4， 1≤N≤10^{18}， 1≤K≤10^15 1≤T≤104，1≤N≤1018，1≤K≤1015。 保证一个测试点中不同的 K 的个数至多为 50。
题意即求是否有一组非负整数解 x i x_i xi， ∑ x i ∗ p i = n \sum x_i*p_i=n ∑xi∗pi=n( p i p_i pi为k的所有质因子） 首先对其质因数分解，对质因子个数分类讨论:
1个，即判断 p 1 p_1 p1是否整除n即可;2个，扩欧求出一组解，然后调整将其中一个变为最小的非负数，判断乘积是否小于等于n即可;多于2个，显然最小的质因子不超过105，记作 p 0 p_0 p0，同时如果 n = x n = x n=x可行，则 n = x + k p 0 n=x+kp_0 n=x+kp0也可行，因此只需要找到 ∀ 0 ≤ T < p 0 {\forall}0 \le T< p_0 ∀0≤T<p0，找到最小的 n = a ( m o d p 0 ) n = a(mod\ p_0) n=a(mod p0) 使得n可行.具体的，可以看作最短路，将 ( i , ( i + p j ) m o d p 0 ) ( j > 0 ) (i,(i+p_j)mod p_0) (j>0) (i,(i+pj)modp0)(j>0)连边，之后求出0到x的最短路即为最小的n，用dij算法即可。
该代码要256MB的内存限制
#pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef long long LL; const int Q=55; const int LOG=64; const int N=1e5+5; const int P=2e6+5; const int V=3.2e7+5; const LL INF=4e18; template <typename T> void read(T &x) { x=0; int f=1; char c=getchar(); for(; !isdigit(c); c=getchar()) if(c=='-') f=-f; for(; isdigit(c); c=getchar()) x=x*10+c-'0'; x*=f; } template <typename T> void write(T x) { if(x<0) x=-x,putchar('-'); if(x>9) write(x/10); putchar(x%10+'0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int q,tot; int prime[Q],f[V],cnt[Q]; LL memk[Q]; LL p[Q][LOG],dist[Q][N]; struct info { long long dist; int home; }; bool operator < (info a, info b) { return a.dist > b.dist; } void exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return; } LL q=a/b,r=a%b; exgcd(b,r,y,x); y-=q*x; } int main() { freopen("fantasy.in","r",stdin); freopen("fantasy.out","w",stdout); int num; read(num); for (int i=2; i<V; i++) { if(f[i]==0) prime[++tot]=f[i]=i; for (int j=1; j<=tot && prime[j]<=f[i]; j++) { int tmp=prime[j]*i; if(tmp>=V) break; f[tmp]=prime[j]; } } int T; read(T); while(T--) { LL n, k; read(n),read(k); int pos=0; for(int i=1; i<=q; i++) if(memk[i]==k) pos=i; if(pos==0) { pos=++q; memk[q]=k; LL tmp=k; for(int i=1; 1LL*prime[i]*prime[i]<=tmp; i++) if(tmp%prime[i]==0) { p[pos][++cnt[pos]]=prime[i]; while(tmp%prime[i]==0) tmp/=prime[i]; } if(tmp!=1) p[pos][++cnt[pos]]=tmp; if(cnt[pos]>=3) { for(int i=0; i<p[pos][1]; i++) dist[pos][i]=INF; static priority_queue <info> Heap; dist[pos][0]=0; Heap.push((info){0,0}); static bool vis[N]; memset(vis,0,sizeof(vis)); while(!Heap.empty()) { while(!Heap.empty() && vis[Heap.top().home]) Heap.pop(); if(Heap.empty()) break; info tmp=Heap.top(); Heap.pop(); for(int i=2; i<=cnt[pos]; i++) { int dest=(tmp.home+p[pos][i])%p[pos][1]; if (dist[pos][dest]>tmp.dist+p[pos][i]) { dist[pos][dest]=tmp.dist+p[pos][i]; Heap.push((info){dist[pos][dest],dest}); } } } } } bool flg=0; for(int i=1; i<=cnt[pos]; i++) if(n%p[pos][i]==0) { printf("YES\n"); flg=1; break; } if(flg) continue; if(cnt[pos]<=1) { printf("NO\n"); continue; } if(cnt[pos]==2) { LL x=0,y=0; exgcd(p[pos][1],p[pos][2],x,y); y=(y%p[pos][1]+p[pos][1])%p[pos][1]; LL tmp=y*(n%p[pos][1])%p[pos][1]*p[pos][2]; if(tmp<=n) printf("YES\n"); else printf("NO\n"); continue; } int tmp=n%p[pos][1]; if(dist[pos][tmp]<=n) printf("YES\n"); else printf("NO\n"); } return 0; }