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。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
struct in{
ll num,cnt[10],sum;
in(){num=sum=0; memset(cnt,0,sizeof(cnt)); }
}dp[16];
int q[20],tot,vis[16];
in dfs(int pos,int st,int lim)
{
if(!lim&&vis[pos]) return dp[pos];
if(pos==1) {
in res; res.num=1;
return res;
}
int up=9; in res,tmp; if(lim) up=q[pos-1];
rep(i,0,up){
tmp=dfs(pos-1,i,lim&&i==up);
res.sum+=tmp.sum;
rep(j,i+1,9) res.sum+=tmp.cnt[j];
rep(j,0,9) res.cnt[j]+=tmp.cnt[j];
res.cnt[i]+=tmp.num;
res.num+=tmp.num;
}
vis[pos]=1;
return dp[pos]=res;
}
ll cal(ll x)
{
if(x<10) return 0;
tot=0; ll ans=0;
while(x) q[++tot]=x%10,x/=10;
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
rep(i,1,tot){
ll up=9; if(i==tot) up=q[tot];
rep(j,1,up){
in tmp=dfs(i,j,(i==tot)&&(j==q[tot]));
ans+=tmp.sum;
rep(k,j+1,9) ans+=1LL*tmp.cnt[k];
}
}
return ans;
}
int main()
{
ll L,R; int T,Ca=0; scanf("%d",&T);
while(T--){
scanf("%lld%lld",&L,&R);
printf("Case %d: %lld\n",++Ca,cal(R)-cal(L-1));
}
return 0;
}
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; 而阶乘的唯一分解只需要一直除即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1000010;
const int Mod=1e7+7;
int a[maxn],N,p[maxn],vis[maxn],cnt;ll ans=1;
int solve(int p)
{
int tN=N,res=0;
while(tN) {
res+=tN/p;
if(res>Mod) res-=Mod;
tN/=p;
} return res;
}
int get(int p)
{
if(p&1) return 1LL*(p+1)/2*p%Mod;
return 1LL*p/2*(p+1)%Mod;
}
int main()
{
rep(i,2,1000000){
if(!vis[i]) p[++cnt]=i;
for(int j=1;j<=cnt&&p[j]*i<=1000000;j++){
vis[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
while(~scanf("%d",&N)&N){
ans=1;
rep(i,2,N) {
if(!vis[i]) a[i]=solve(i);
}
rep(i,2,N){
if(a[i])
ans=(ll)ans*get(a[i]+1)%Mod;
}
printf("%lld\n",ans);
}
return 0;
}
E.Helping the HR
题意：给定每个人的签到和离开时间，问每个人的..情况
思路：模拟； by许。
#include<bits/stdc++.h>
using namespace std;
char str[30];
int main()
{
int n,s=17*1800,D=19*1800,E=25*1800;
while(~scanf("%d",&n)&&n)
{
int cnt=0;
for(int cas=0;cas<n;cas++)
{
int S=0,T=0,tot=0,pre=0,p=3600;
scanf("%s",str);
int len=strlen(str);
for(int i=2;i<len;i++)
{
if(str[i]!=':'&&i!=len-1)pre=pre*10+str[i]-'0';
else
{
if(i==len-1)pre=pre*10+str[i]-'0';
tot++;
if(tot<=3)
{
S+=pre*p;
if(tot==3)p=3600;
else p/=60;
}
else T+=pre*p,p/=60;
pre=0;
}
}
int flag=0;
if(str[0]=='D'&&S>D)flag=1;
if(str[0]=='E'&&S>E)flag=1;
int res=T-max(s,S);
if(str[0]=='D'&&res<8*3600)flag=1;
if(str[0]=='E'&&res<9*3600)flag=1;
cnt+=flag;
}
if(!cnt)puts("All OK");
else if(cnt<=3)printf("%d Point(s) Deducted\n",cnt);
else puts("Issue Show Cause Letter");
}
}
F .Path Intersection
题意：给定一棵树, Q次询问，每次给定K条路经，求这K条路有多少个公共点.
思路：路剖, 即每条路经+1， 然后可以选一条路径看有多少个点被覆盖K次。
好久没写树剖了，开始写错的地方提醒下自己： 当top不同的时候，我们先操作dep[top[]]大的，然后把它变为fa[top[]];
而top相同的，正常的从小到大即可。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
int Laxt[maxn],Next[maxn],To[maxn],cnt,dep[maxn];
int sz[maxn],son[maxn],top[maxn],pos[maxn],N;
int Mx[maxn],num[maxn],Lazy[maxn],fa[maxn],tot;
void add(int u,int v){
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;
}
void dfs1(int u,int f)
{
sz[u]=1; fa[u]=f;
dep[u]=dep[f]+1; son[u]=0;
for(int i=Laxt[u];i;i=Next[i]){
if(To[i]!=f){
dfs1(To[i],u);
if(sz[To[i]]>sz[son[u]]) son[u]=To[i];
}
}
}
void dfs2(int u,int Top)
{
pos[u]=++tot; top[u]=Top;
if(son[u]) dfs2(son[u],Top);
for(int i=Laxt[u];i;i=Next[i]){
if(To[i]!=fa[u]&&To[i]!=son[u])
dfs2(To[i],To[i]);
}
}
void build(int Now,int L,int R)
{
Mx[Now]=Lazy[Now]=0; num[Now]=R-L+1;
if(L==R) return; int Mid=(L+R)>>1;
build(Now<<1,L,Mid); build(Now<<1|1,Mid+1,R);
}
void pushdown(int Now)
{
if(Lazy[Now]) {
Mx[Now<<1]+=Lazy[Now];Lazy[Now<<1]+=Lazy[Now];
Mx[Now<<1|1]+=Lazy[Now];Lazy[Now<<1|1]+=Lazy[Now];
Lazy[Now]=0;
}
}
void pushup(int Now)
{
Mx[Now]=Mx[Now<<1]; num[Now]=num[Now<<1];
if(Mx[Now<<1|1]>Mx[Now])
Mx[Now]=Mx[Now<<1|1],num[Now]=num[Now<<1|1];
else if(Mx[Now<<1|1]==Mx[Now])
num[Now]+=num[Now<<1|1];
}
void update(int Now,int L,int R,int l,int r,int val)
{
if(l<=L&&r>=R){
Mx[Now]+=val; Lazy[Now]+=val; return ;
}
pushdown(Now); int Mid=(L+R)>>1;
if(l<=Mid) update(Now<<1,L,Mid,l,r,val);
if(r>Mid) update(Now<<1|1,Mid+1,R,l,r,val);
pushup(Now);
}
int query(int Now,int L,int R,int l,int r,int K)
{
if(Mx[Now]<K) return 0;
if(l<=L&&r>=R) return Mx[Now]==K?num[Now]:0;
pushdown(Now); int Mid=(L+R)>>1,res=0;
if(l<=Mid) res+=query(Now<<1,L,Mid,l,r,K);
if(r>Mid) res+=query(Now<<1|1,Mid+1,R,l,r,K);
pushup(Now); return res;
}
void pathup(int u,int v,int val)
{
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(1,1,N,pos[top[u]],pos[u],val);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(1,1,N,pos[u],pos[v],val);
}
int pathquery(int u,int v,int K)
{
int res=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=query(1,1,N,pos[top[u]],pos[u],K);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res+=query(1,1,N,pos[u],pos[v],K);
return res;
}
int a[maxn],b[maxn];
int main()
{
int T,Q,K,C=0,u,v;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
rep(i,1,N) Laxt[i]=0; cnt=0; tot=0;
rep(i,1,N-1){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs1(1,0); dfs2(1,1);
build(1,1,N);
scanf("%d",&Q);
printf("Case %d:\n",++C);
while(Q--){
scanf("%d",&K);
rep(i,1,K) scanf("%d%d",&a[i],&b[i]);
rep(i,1,K) pathup(a[i],b[i],1);
printf("%d\n",pathquery(a[1],b[1],K));
rep(i,1,K) pathup(a[i],b[i],-1);
}
}
return 0;
}
I .Triangles
题意：给定两个三维空间里的三角形，求最近距离。
思路：好像是不错的题，想补。
J. VAT Man
签到。 by许。
#include<bits/stdc++.h>
#define db double
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
db x;
cin>>x;
printf("%.2lf\n",x*1.15);
}
}
