1001 质数筛选 判断公共因子
题意:判断A进制下的有限小数 能否转化成B进制下的有限小数。
题解给的是,只需要判断B中质因子是否包含A中质因子即可。不是很明白,后来问了群里的大牛,现在也算明白些了。
整数部分的互相转换不用考虑,一定可以转换的,A进制转化成十进制的小数形式是(1/A + 1/A^2 + 1/A^3 + ... + 1/A^n) 系数不用考虑,想想十进制化二进制的时候是每次都乘以2取整什么的,所以要化成B进制小数,并且保证最后是有限小数,那么需要(1/A^x)*B^k 为整数,()前的系数不影响,一个整数可以分解成p1^a1*p2*a2...pn^an(质因数分解)的形式,所以只要B的质因子包含A的质因子即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const int maxn = 1000010; int isprime[maxn] = {0}; int prime[maxn]; ll ans[maxn]; int main() { int i , j; for(i = 2 ; i*i < maxn ; i ++) if(!isprime[i]) for(j = i+i ; j < maxn ; j += i) isprime[j] = 1; int g = 0; for(i = 2 ; i < maxn ; i ++) { if(!isprime[i]) prime[g++] = i; } int T; int cas = 1; scanf("%d",&T); while(T--) { ll t = 0; ll A , B; cin>>A>>B; int sus = 1; for(i = 0 ; prime[i]<=A && prime[i] ; i ++) { int flag = 0; if(A%prime[i]==0) { if(B%prime[i]!=0) { sus = 0; break; } } while(A%prime[i]==0) A/=prime[i]; } if(A!=1 && B%A!=0) sus = 0; //A没有约到1 但是每次约的时候 B也跟着除了 if(sus) printf("Case #%d: YES\n",cas++); else printf("Case #%d: NO\n",cas++); } }
1005 判环
题意:给出一个有向图图,保证两两点之间一定有边,求是否存在三个点的环。
思路:看官方题解。。。没看明白,后来往上看的什么判环。。画了画,果然,只要图中有环,那么一定存在三元环,因为两两点之间必定有边,可以用4个点5个点试试。所以用拓扑排序判环就行,但是用DFS判环一直TLE、、、
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 2010; int map[maxn][maxn]; char s[maxn][maxn]; int main() { int T , cas = 1; int indegree[maxn]; scanf("%d",&T); while(T--) { int n; memset(indegree , 0 , sizeof(indegree)); scanf("%d",&n); int i , j; for(i = 1 ; i <= n ; i ++) scanf("%s",s[i]+1); for(i = 1 ; i <= n ; i ++) for(j = 1 ; j <= n ; j ++) { map[i][j] = s[i][j] - '0'; if(map[i][j]) { indegree[j]++; //printf("%d %d\n",i,j); } } int k , m = 0; for(i = 1 ; i <= n ; i ++) { for(j = 1 ; j <= n ; j ++) { if(indegree[j]==0) { indegree[j] = -1;//删点 m++; for(k = 1 ; k <= n ; k ++) { if(map[j][k]) { map[j][k] = 0; indegree[k]--; } } break; } } } //printf("%d\n",m); if(m!=n) printf("Case #%d: Yes\n",cas++); else printf("Case #%d: No\n",cas++); } }
还有一个。。。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxn = 2010; const int maxm = 2100000; struct edge{ int v; int nex; }e[maxm]; int k , head[maxn]; void addedge(int a , int b) { e[k].v = b; e[k].nex = head[a]; head[a] = k++; } char s[maxn][maxn]; int indegree[maxn]; int main() { int T , cas = 1; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i = 1 ; i <= n ; i ++) scanf("%s",s[i]+1); int a , b; k = 1; memset(head , -1 , sizeof(head)); memset(indegree , 0 , sizeof(indegree)); for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= n ; j ++) { if(s[i][j]-'0'>0) { a = i; b = j; addedge(a , b); indegree[b]++; } } int flag = 0 , p = 0; queue<int> q; for(int i = 1 ; i <= n ; i ++) { if(indegree[i]==0) { q.push(i); p = 1; } } if(!p) { printf("Case #%d: Yes\n",cas++); continue; } int m = 0; while(!q.empty()) { int t = q.front(); q.pop(); m++; for(int j = head[t] ; j != -1 ; j = e[j].nex) { int v = e[j].v; indegree[v]--; if(indegree[v]==0) q.push(v); } } if(m!=n) printf("Case #%d: Yes\n",cas++); else printf("Case #%d: No\n",cas++); } }
1006 线段树
题意:给出一些区间代表花开的时间段,询问的时候给出时间点,问这个时候有多少花是开着的。
思路:线段树+lazy+离散化
这道题看人人上思路后尝试着自己搞,也是用的离散化,但是总超时。。。也许写的也不对,后来就看别人没有离散化的版本给A了,今天又看到这个
http://www.cnblogs.com/Yu2012/archive/2012/08/09/2630444.html HH版本的线段树 用的离散化。 发现我写的还是有毛病,思路不清晰,细节不注意,总之线段树还是不熟练。。。而且最坑爹的是写的差不多了,cout ..2000ms+超时 printf直接过。。擦的
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define lson l , m , rt<<1 #define rson m + 1 , r , rt<<1|1 const int maxn = 100100; int X[maxn<<2]; int li[maxn] , ri[maxn] , qq[maxn]; int add[maxn<<2]; //lazy int sum[maxn<<2]; //该区间内出现了花开的次数 int ans; void Pushdown(int rt) { //节点编号 区间长度 if(add[rt]!=0) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; sum[rt<<1] += add[rt]; sum[rt<<1|1] += add[rt]; add[rt] = 0; //printf("向下更新\n"); } } int Bin(int key , int n , int X[]) { int l = 0; int r = n - 1; int m , k = -1; while(l <= r) { m = (l + r)>>1; if(key >= X[m]) { k = m; l = m + 1; } else r = m - 1; } return k; } void build(int l , int r , int rt) { add[rt] = 0; sum[rt] = 0; if(l == r) return; int m = (l + r)>>1; //printf("%d %d %d\n",l,r,rt); build(lson); build(rson); } void Update(int L , int R , int l , int r , int rt) { //printf("%d %d %d %d %d\n",L,R,l,r,rt); if(L<=l && R>=r) { add[rt] ++; sum[rt] ++; return; } Pushdown(rt); int m = (l + r)>>1; if(m >= L) Update(L , R , lson); if(m < R) Update(L , R , rson); } int Query(int L , int R , int l , int r , int rt) { if(L <= l && R >= r) { return sum[rt]; } Pushdown(rt); //if(l == r) return sum[rt]; int ret = 0; int m = (l + r)>>1; if(m >= L) ret += Query(L , R , lson); if(m < R) ret += Query(L , R , rson); return ret; } int main() { int T; int cas = 1; scanf("%d",&T); while(T--) { int u , q , i; scanf("%d%d",&u,&q); int g = 0; for(i = 0 ; i < u ; i ++) { scanf("%d%d",&li[i],&ri[i]); X[g++] = li[i]; X[g++] = ri[i]; } for(i = 0 ; i < q ; i ++) { scanf("%d",&qq[i]); X[g++] = qq[i]; } sort(X , X + g); int m = 1; for(i = 1 ; i < g ; i ++) { //去重 if(X[i]!=X[i-1]) X[m++] = X[i]; } build(0 , m , 1); for(i = 0 ; i < u ; i ++) { int l = Bin(li[i] , m , X); int r = Bin(ri[i] , m , X); Update(l , r , 0 , m , 1); } int tq; printf("Case #%d:\n",cas++); for(i = 0 ; i < q ; i ++) { ans = 0; int key = Bin(qq[i] , m , X); printf("%d\n",Query(key , key , 0 , m , 1)); //就这里改成cout 超时坑死你! } } }