B .Counting Inversion
**题意：**给定L,R，求这个区间的逆序对数之和。(L,R<1e15)
**思路：**一看这个范围就知道是数位DP。 只是维护的东西稍微多一点，需要记录后面的各种数字的个数cnt，以及逆序对和sum，以及出现了多少种后缀num。
那么枚举到当前位时，假设为i ，那么sum+=cnt[i+1]+cnt[i+2]+....cnt[9]; cnt[i]+=num; 可以参考CF1073E。
1#include<bits/stdc++.h> 2#define rep(i,a,b) for(int i=a;i<=b;i++) 3#define ll long long 4using namespace std; 5struct in{ 6 ll num,cnt[10],sum; 7 in(){num=sum=0; memset(cnt,0,sizeof(cnt)); } 8}dp[16]; 9int q[20],tot,vis[16]; 10in dfs(int pos,int st,int lim) 11{ 12 if(!lim&&vis[pos]) return dp[pos]; 13 if(pos==1) { 14 in res; res.num=1; 15 return res; 16 } 17 int up=9; in res,tmp; if(lim) up=q[pos-1]; 18 rep(i,0,up){ 19 tmp=dfs(pos-1,i,lim&&i==up); 20 res.sum+=tmp.sum; 21 rep(j,i+1,9) res.sum+=tmp.cnt[j]; 22 rep(j,0,9) res.cnt[j]+=tmp.cnt[j]; 23 res.cnt[i]+=tmp.num; 24 res.num+=tmp.num; 25 } 26 vis[pos]=1; 27 return dp[pos]=res; 28} 29ll cal(ll x) 30{ 31 if(x<10) return 0; 32 tot=0; ll ans=0; 33 while(x) q[++tot]=x%10,x/=10; 34 memset(dp,0,sizeof(dp)); 35 memset(vis,0,sizeof(vis)); 36 rep(i,1,tot){ 37 ll up=9; if(i==tot) up=q[tot]; 38 rep(j,1,up){ 39 in tmp=dfs(i,j,(i==tot)&&(j==q[tot])); 40 ans+=tmp.sum; 41 rep(k,j+1,9) ans+=1LL*tmp.cnt[k]; 42 } 43 } 44 return ans; 45} 46int main() 47{ 48 ll L,R; int T,Ca=0; scanf("%d",&T); 49 while(T--){ 50 scanf("%lld%lld",&L,&R); 51 printf("Case %d: %lld\n",++Ca,cal(R)-cal(L-1)); 52 } 53 return 0; 54}
C .Divisors of the Divisors of An Integer
**题意：**给出N，问N！的因子的因子个数和。
**思路：**唯一分解，对于一个素数p，假设它的幂次是x，那么因子的幂次有0，1，2，...x；那么因子的因子幂次就是(0)； (0，1)； ( 0，1，2)； ... ; (0，1，2，...x)
所以就是一个累乘，对于每个素数p，ans*=(x+1)*(x+2)/2; 而阶乘的唯一分解只需要一直除即可。
1#include<bits/stdc++.h> 2#define ll long long 3#define rep(i,a,b) for(int i=a;i<=b;i++) 4using namespace std; 5const int maxn=1000010; 6const int Mod=1e7+7; 7int a[maxn],N,p[maxn],vis[maxn],cnt;ll ans=1; 8int solve(int p) 9{ 10 int tN=N,res=0; 11 while(tN) { 12 res+=tN/p; 13 if(res>Mod) res-=Mod; 14 tN/=p; 15 } return res; 16} 17int get(int p) 18{ 19 if(p&1) return 1LL*(p+1)/2*p%Mod; 20 return 1LL*p/2*(p+1)%Mod; 21} 22int main() 23{ 24 rep(i,2,1000000){ 25 if(!vis[i]) p[++cnt]=i; 26 for(int j=1;j<=cnt&&p[j]*i<=1000000;j++){ 27 vis[p[j]*i]=1; 28 if(i%p[j]==0) break; 29 } 30 } 31 while(~scanf("%d",&N)&N){ 32 ans=1; 33 rep(i,2,N) { 34 if(!vis[i]) a[i]=solve(i); 35 } 36 rep(i,2,N){ 37 if(a[i]) 38 ans=(ll)ans*get(a[i]+1)%Mod; 39 } 40 printf("%lld\n",ans); 41 } 42 return 0; 43}
E.Helping the HR
**题意：**给定每个人的签到和离开时间，问每个人的..情况
**思路：**模拟； by许。
1#include<bits/stdc++.h> 2using namespace std; 3char str[30]; 4int main() 5{ 6 int n,s=17*1800,D=19*1800,E=25*1800; 7 while(~scanf("%d",&n)&&n) 8 { 9 int cnt=0; 10 for(int cas=0;cas<n;cas++) 11 { 12 int S=0,T=0,tot=0,pre=0,p=3600; 13 scanf("%s",str); 14 int len=strlen(str); 15 for(int i=2;i<len;i++) 16 { 17 if(str[i]!=':'&&i!=len-1)pre=pre*10+str[i]-'0'; 18 else 19 { 20 if(i==len-1)pre=pre*10+str[i]-'0'; 21 tot++; 22 if(tot<=3) 23 { 24 S+=pre*p; 25 if(tot==3)p=3600; 26 else p/=60; 27 } 28 else T+=pre*p,p/=60; 29 pre=0; 30 } 31 } 32 int flag=0; 33 if(str[0]=='D'&&S>D)flag=1; 34 if(str[0]=='E'&&S>E)flag=1; 35 int res=T-max(s,S); 36 if(str[0]=='D'&&res<8*3600)flag=1; 37 if(str[0]=='E'&&res<9*3600)flag=1; 38 cnt+=flag; 39 } 40 if(!cnt)puts("All OK"); 41 else if(cnt<=3)printf("%d Point(s) Deducted\n",cnt); 42 else puts("Issue Show Cause Letter"); 43 } 44}
F .Path Intersection
**题意：**给定一棵树, Q次询问，每次给定K条路经，求这K条路有多少个公共点.
**思路：**路剖, 即每条路经+1， 然后可以选一条路径看有多少个点被覆盖K次。
好久没写树剖了，开始写错的地方提醒下自己： 当top不同的时候，我们先操作dep[top[]]大的，然后把它变为fa[top[]];
而top相同的，正常的从小到大即可。
1#include<bits/stdc++.h> 2#define rep(i,a,b) for(int i=a;i<=b;i++) 3using namespace std; 4const int maxn=200010; 5int Laxt[maxn],Next[maxn],To[maxn],cnt,dep[maxn]; 6int sz[maxn],son[maxn],top[maxn],pos[maxn],N; 7int Mx[maxn],num[maxn],Lazy[maxn],fa[maxn],tot; 8void add(int u,int v){ 9 Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; 10} 11void dfs1(int u,int f) 12{ 13 sz[u]=1; fa[u]=f; 14 dep[u]=dep[f]+1; son[u]=0; 15 for(int i=Laxt[u];i;i=Next[i]){ 16 if(To[i]!=f){ 17 dfs1(To[i],u); 18 if(sz[To[i]]>sz[son[u]]) son[u]=To[i]; 19 } 20 } 21} 22void dfs2(int u,int Top) 23{ 24 pos[u]=++tot; top[u]=Top; 25 if(son[u]) dfs2(son[u],Top); 26 for(int i=Laxt[u];i;i=Next[i]){ 27 if(To[i]!=fa[u]&&To[i]!=son[u]) 28 dfs2(To[i],To[i]); 29 } 30} 31void build(int Now,int L,int R) 32{ 33 Mx[Now]=Lazy[Now]=0; num[Now]=R-L+1; 34 if(L==R) return; int Mid=(L+R)>>1; 35 build(Now<<1,L,Mid); build(Now<<1|1,Mid+1,R); 36} 37void pushdown(int Now) 38{ 39 if(Lazy[Now]) { 40 Mx[Now<<1]+=Lazy[Now];Lazy[Now<<1]+=Lazy[Now]; 41 Mx[Now<<1|1]+=Lazy[Now];Lazy[Now<<1|1]+=Lazy[Now]; 42 Lazy[Now]=0; 43 } 44} 45void pushup(int Now) 46{ 47 Mx[Now]=Mx[Now<<1]; num[Now]=num[Now<<1]; 48 if(Mx[Now<<1|1]>Mx[Now]) 49 Mx[Now]=Mx[Now<<1|1],num[Now]=num[Now<<1|1]; 50 else if(Mx[Now<<1|1]==Mx[Now]) 51 num[Now]+=num[Now<<1|1]; 52} 53void update(int Now,int L,int R,int l,int r,int val) 54{ 55 if(l<=L&&r>=R){ 56 Mx[Now]+=val; Lazy[Now]+=val; return ; 57 } 58 pushdown(Now); int Mid=(L+R)>>1; 59 if(l<=Mid) update(Now<<1,L,Mid,l,r,val); 60 if(r>Mid) update(Now<<1|1,Mid+1,R,l,r,val); 61 pushup(Now); 62} 63int query(int Now,int L,int R,int l,int r,int K) 64{ 65 if(Mx[Now]<K) return 0; 66 if(l<=L&&r>=R) return Mx[Now]==K?num[Now]:0; 67 pushdown(Now); int Mid=(L+R)>>1,res=0; 68 if(l<=Mid) res+=query(Now<<1,L,Mid,l,r,K); 69 if(r>Mid) res+=query(Now<<1|1,Mid+1,R,l,r,K); 70 pushup(Now); return res; 71} 72void pathup(int u,int v,int val) 73{ 74 while(top[u]!=top[v]){ 75 if(dep[top[u]]<dep[top[v]]) swap(u,v); 76 update(1,1,N,pos[top[u]],pos[u],val); 77 u=fa[top[u]]; 78 } 79 if(dep[u]>dep[v]) swap(u,v); 80 update(1,1,N,pos[u],pos[v],val); 81} 82int pathquery(int u,int v,int K) 83{ 84 int res=0; 85 while(top[u]!=top[v]){ 86 if(dep[top[u]]<dep[top[v]]) swap(u,v); 87 res+=query(1,1,N,pos[top[u]],pos[u],K); 88 u=fa[top[u]]; 89 } 90 if(dep[u]>dep[v]) swap(u,v); 91 res+=query(1,1,N,pos[u],pos[v],K); 92 return res; 93} 94int a[maxn],b[maxn]; 95int main() 96{ 97 int T,Q,K,C=0,u,v; 98 scanf("%d",&T); 99 while(T--){ 100 scanf("%d",&N); 101 rep(i,1,N) Laxt[i]=0; cnt=0; tot=0; 102 rep(i,1,N-1){ 103 scanf("%d%d",&u,&v); 104 add(u,v); add(v,u); 105 } 106 dfs1(1,0); dfs2(1,1); 107 build(1,1,N); 108 scanf("%d",&Q); 109 printf("Case %d:\n",++C); 110 while(Q--){ 111 scanf("%d",&K); 112 rep(i,1,K) scanf("%d%d",&a[i],&b[i]); 113 rep(i,1,K) pathup(a[i],b[i],1); 114 printf("%d\n",pathquery(a[1],b[1],K)); 115 rep(i,1,K) pathup(a[i],b[i],-1); 116 } 117 } 118 return 0; 119}
I .Triangles
**题意：**给定两个三维空间里的三角形，求最近距离。
**思路：**好像是不错的题，想补。
J. VAT Man
签到。 by许。
1#include<bits/stdc++.h> 2#define db double 3using namespace std; 4int main() 5{ 6 int T; 7 cin>>T; 8 while(T--) 9 { 10 db x; 11 cin>>x; 12 printf("%.2lf\n",x*1.15); 13 } 14}