1001 Primes Problem
打个10^4的素数表，枚举前两个搞一下就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<vector> #include<stdlib.h> #include<algorithm> #include<math.h> using namespace std; const int n = 10000; int vis[11111]; int cnt ; int ans[11111]; void gao() { memset(vis,0,sizeof(vis)); for(int i= 2;i<=sqrt(n);i++){ for(int j= 2;i*j<=n;j++) if(!vis[i]) vis[i*j] = 1; } vis[0] = 1;vis[1] = 1; cnt = 0; for(int i = 2;i<=n;i++) if(!vis[i]) ans[cnt++] = i; } int main() { gao(); int k; while(cin>>k){ int sum = 0; for(int i = 0;i<cnt;i++){ if(ans[i]>=k) continue; for(int j=i;j<cnt;j++){ int t = k-ans[i]-ans[j]; if(t<=0) break; if(vis[t]||t<ans[j]) continue; else sum++; } } printf("%d ",sum); } return 0; }
1002 Math Problem
解方程啊，预测数据太水，我没加根号都能过预测，无语。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<vector> #include<stdlib.h> #include<algorithm> #include<math.h> using namespace std; #define eps = 1e-7 double a,b,c,d,L,R; double x1,x2; int gao() { double t = 4*b*b - 12*a*c; if(t<0) return 0; else{ x1 = (-2) * b + sqrt(t); x1/=6*a; x2 = (-2)*b - sqrt(t); x2/=6*a; } return 1; } double qiu(double x) { double t = a*x*x*x + b*x*x + c*x +d; return fabs(t); } double qiu1(double x) { double t = b*x*x + c*x+d; return fabs(t); } int main() { double t1,t2; while(cin>>a>>b>>c>>d>>L>>R){ t1 = qiu(L);t2 = qiu(R); if(a==0){ if(b==0){ printf("%.2lf ",max(t1,t2)); } else{ double t4 = (-c) / (2*b); if(t4>=L&&t4<=R){ double t3 = qiu1((-c)/(2*b)); t1 = max(t1,t2); t1 =max(t1,t3); printf("%.2lf ",t1); } else{ printf("%.2lf ",max(t1,t2)); } } continue; } if(!gao()){ printf("%.2lf ",max(t1,t2)); continue; } else{ double t3 = qiu(x1) ;double t4 = qiu(x2); t3 = max(t3,t4); t1 = max(t1,t2); printf("%.2lf ",max(t1,t3)); } } return 0; }
1003 Bits Problem
数位dp，记录一个的到当前位满足条件的1的种类数，记录一个到当前位满足条件的数的和
因为是开区间，最后单独判断一下右端点。
#include<stdio.h> #include<string.h> #include<vector> #include<iostream> #include<map> #include<queue> using namespace std; const int mod = 1e9+7; typedef long long LL; const int maxn = 1111; int dp_sum[maxn][maxn]; int dp_mod[maxn][maxn]; int n; int val[maxn]; char str[maxn]; int dfs_sum(int x,int sum,int flag) { if(~dp_sum[x][sum]&&!flag) return dp_sum[x][sum]; int bound = flag? val[x]:1; if(x==0){ if(sum==0)return 1; else return 0; } int ans = 0 ; for(int i = 0 ;i<=bound;i++){ if(i==0) ans+=dfs_sum(x-1,sum,flag&&bound==i),ans%=mod; else{ if(sum>0) ans+=dfs_sum(x-1,sum-1,flag&&bound==i),ans%=mod; } } return flag? ans:dp_sum[x][sum] = ans; } LL cifang(LL a,int b) { LL ans = 1; while(b){ if(b&1) ans*=a,ans%=mod; a*=a;a%=mod; b>>=1; } return ans; } LL dfs_mod(int x,int sum,int flag) { if(~dp_mod[x][sum]&&!flag) return dp_mod[x][sum]; int bound = flag? val[x] : 1; if(x==0) return 0; LL ans = 0 ; for(int i = 0 ;i<=bound;i++){ if(i==0){ ans+=dfs_mod(x-1,sum,flag&&bound==i),ans%=mod; } else{ if(sum<=0) continue; int t = dfs_sum(x-1,sum-1,flag&&bound == i ); ans+=t%mod*cifang(2,x-1)%mod; ans+=dfs_mod(x-1,sum-1,flag&&bound==i),ans%=mod; } } return flag?ans:dp_mod[x][sum] = ans; } void gao() { int len =strlen(str); for(int i = 0 ;i<len;i++){ val[i+1] = str[len-i-1] - '0'; } LL t = dfs_mod(len,n,1); int ans = 0; int cnt = 0; for(int i = len;i>=1;i--) if(val[i]) cnt++; for(int i = len;i>=1;i--){ ans=ans*2+val[i];ans%=mod; } if(cnt==n) t-=ans; if(t<0) t = (t+mod) % mod; printf("%I64d ",t); } int main() { memset(dp_sum,-1,sizeof(dp_sum)); memset(dp_mod,-1,sizeof(dp_mod)); // system("pause"); while(scanf("%d",&n)!=EOF){ scanf("%s",str); gao(); } return 0; }
1004 K-short Problem
先离散化。
k最大为10嘛，每个节点记录从小到大记录十个数。
按x从小到大，y从小到大，h从小到大
以y轴建树
离线更新查询同时进行 ，线段树上的操作暴力搞就好。
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <set> #include <bitset> #include <queue> #include <stack> #include <string> #include <iostream> #include <cmath> #include <climits> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int maxn = 66666; vector<int> node[maxn<<2]; vector<int> gg; int n,m; vector<int> ans; int val[maxn]; struct Node { int x;int y;int h;int pos; }edge[maxn],edge1[maxn]; int len; int cmp(const Node &a,const Node &b) { if(a.x!=b.x) return a.x<b.x; if(a.y!=b.y) return a.y<b.y; return a.h<b.h; } void gao1() { gg.clear(); for(int i = 0;i<n;i++) gg.push_back(edge[i].y); for(int i = 0;i<m;i++) gg.push_back(edge1[i].y); sort(gg.begin(),gg.end()); gg.erase(unique(gg.begin(),gg.end()),gg.end()); for(int i = 0;i<n;i++) edge[i].y = lower_bound(gg.begin(),gg.end(),edge[i].y) - gg.begin(); for(int i =0;i<m;i++) edge1[i].y = lower_bound(gg.begin(),gg.end(),edge1[i].y) - gg.begin(); len = gg.size() - 1; } void up(int rt) { node[rt].clear(); int a[22];int cnt = 0; for(int i= 0;i<node[rt<<1].size();i++){ a[cnt++] = node[rt<<1][i]; } for(int i =0;i<node[rt<<1|1].size();i++){ a[cnt++] = node[rt<<1|1][i]; } sort(a,a+cnt); cnt = min(cnt,10); for(int i =0;i<cnt;i++) node[rt].push_back(a[i]); } void build(int l,int r,int rt) { node[rt].clear(); if(l==r) return ; int mid=(l+r)>>1; build(lson); build(rson); } void update(int key,int add,int l,int r,int rt) { if(l==r){ node[rt].push_back(add); sort(node[rt].begin(),node[rt].end()); return ; } int mid=(l+r)>>1; if(key<=mid) update(key,add,lson); else update(key,add,rson); up(rt); } void ask(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R){ for(int i = 0 ;i<node[rt].size();i++) ans.push_back(node[rt][i]); return ; } int mid=(l+r)>>1; if(L<=mid) ask(L,R,lson); if(R>mid) ask(L,R,rson); } void gao(int L,int R,int k,int l,int r,int rt,int pos) { ans.clear(); ask(L,R,l,r,rt); if(ans.size()<k) val[pos] = -1; else{ sort(ans.begin(),ans.end()); val[pos] = ans[k-1]; } } int main() { while(cin>>n>>m){ for(int i = 0 ;i<n;i++){ scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].h); } for(int i = 0;i<m;i++){ scanf("%d%d%d",&edge1[i].x,&edge1[i].y,&edge1[i].h); edge1[i].pos = i; } gao1(); sort(edge,edge+n,cmp); sort(edge1,edge1+m,cmp); build(0,len,1); int cnt = 0; for(int i = 0;i<m;i++){ while(1){ if(cnt>=n) break; if(edge[cnt].x>edge1[i].x) break; update(edge[cnt].y,edge[cnt].h,0,len,1); cnt++; } gao(0,edge1[i].y,edge1[i].h,0,len,1,edge1[i].pos); } for(int i = 0;i<m;i++){ printf("%d ",val[i]); } } return 0; }