L Let's Play Curling
分析：
转换一下就是 找每两个b之间 最多有多少个a
先离散化 再树状数组维护一下就好
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=2e5+5;
int n,m,cnt,ans;
int a[maxn],b[maxn],t[maxn],tr[maxn];
void upd(int x){
while(x<=maxn)tr[x]++,x+=lowbit(x);
}
int query(int x){
int res=0;
while(x)res+=tr[x],x-=lowbit(x);
return res;
}
void solve();
int main(){
int T;
cin>>T;
while(T--)solve();
return 0;
}
void solve(){
scanf("%d%d",&n,&m);
ans=0;cnt=0;
memset(tr,0,sizeof(tr));
for(int i=1;i<=n;i++)scanf("%d",&a[i]),t[++cnt]=a[i];
for(int i=1;i<=m;i++)scanf("%d",&b[i]),t[++cnt]=b[i];
b[0]=t[++cnt]=0,b[m+1]=t[++cnt]=1e9+7;
sort(t+1,t+1+cnt);
int len=unique(t+1,t+1+cnt)-t-1;
for(int i=1;i<=n;i++){
int id=lower_bound(t+1,t+1+len,a[i])-t;
a[i]=id,upd(a[i]);
}
for(int i=0;i<=m+1;i++){
int id=lower_bound(t+1,t+1+len,b[i])-t;
b[i]=id;
}
sort(b,b+2+m);
for(int i=1;i<=m+1;i++)
ans=max(ans,query(b[i]-1)-query(b[i-1]));
if(!ans)cout<<"Impossible"<<endl;
else cout<<ans<<endl;
}
F.Fireworks
分析：
式子很好列出 关键在于我们担心计算的时候会掉精度 但是最后打出来貌似不会掉
注意点：因为是要求整数 但是三分只有在小数的时候才能准确找到峰值 所以三分整数最终需要判断+1和-1的值
同样也可以三分小数 最终在小数前后位置找
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
double n,m,p;
void solve();
double calc(int x){
return (x*n+m)/(1-pow((10000-p)/10000,x));
}
int main(){
int T;
cin>>T;
while(T--)solve();
return 0;
}
void solve(){
cin>>n>>m>>p;
int l=1,r=1e9,ans;
while(l<=r){
int mid=(l+r)/2;
int midd=(l+mid)/2;
if(calc(mid)-calc(midd)>=1e-8)ans=midd,r=mid-1;
else l=midd+1;
}
int res;
if(calc(ans)-calc(ans-1)>=1e-8)res=ans-1;
if(calc(ans)-calc(ans+1)>=1e-8)ans++;
if(calc(ans)-calc(res)>=1e-8)ans=res;
printf("%.6lf\n",calc(ans));
}
K Co-prime Permutation
签到题
E Evil Coordinate
分析：
很明显 只要障碍不在终点 或者只能朝x轴方向走(只能朝y轴方向走)并且一定会经过障碍点
其他情况一定是能构造出一个方案 使得路径不经过障碍点
分情况写起来很麻烦
题解给出了偷懒的智慧
完全用不着分类讨论
可以证明存在一种答案，使得相同的方向是连续排在一起的（按原字符串中有 1/2/3/4 种字母进行分类讨论）
枚举 UDLR 的 24 种排列即可
只要把所有情况都列出来 再判断即可
总结出经验 遇到分类讨论构造的题目 如果在数据范围允许的情况 可以遍历所有的构造方案
#include<bits/stdc++.h>
using namespace std;
int t,x,y,dx[]={0,0,-1,1},dy[]={1,-1,0,0},dd[200],c[4];
string s,ans,a="UDLR";
void solve()
{
memset(c,0,sizeof c);
scanf("%d%d",&x,&y);
cin>>s;
for(auto ch:s)c[dd[ch]]++;
int xx=c[3]-c[2],yy=c[0]-c[1];
if((xx==x&&yy==y)||(x==0&&y==0)){puts("Impossible");return;}
int q[4]={0,1,2,3};
do
{
xx=0,yy=0;
ans="";
for(int i=0;i<4;i++)
{
int p=q[i];
for(int j=0;j<c[p];j++)
{
ans+=a[p];
xx+=dx[p];
yy+=dy[p];
if(xx==x&&yy==y)goto End;
}
}
cout<<ans<<endl;
return;
End:;
}while(next_permutation(q,q+4));
puts("Impossible");
}
int main()
{
for(int i=0;i<4;i++)dd[a[i]]=i;
scanf("%d",&t);
while(t--)solve();
return 0;
}
M Monster Hunter
分析：
很好分析的一道树形dp问题
因为相连点会造成影响 所以设置dp数组的时候多开一维 表示该点选择与否
dp[u][k][1] 表示u子树选择k个点 并且u选择的最小值
dp[u][k][0]表示u子树选择k个点 并且u不选择的最小值
不选择的点默认只能用魔法消掉
注意点：一开始一直觉得dfs里面两重循环会爆掉 但是实际上这个题目不会
在剪枝的条件下 具体复杂度肯定比三方小很多 比平方要大些
上下限都需要剪枝 不剪枝会TLE！！！！！！
总结一下就是：在n方的复杂度下是能够进行树上背包的 但是必须上下限都得剪枝
#include<bits/stdc++.h>
using namespace std;
int tot,g[2001],sz[2001],a[2001];
long long dp[2001][2001][2];
struct edge{
int to,next;
}e[1000001];
void add(int a,int b)
{
tot++;
e[tot].to=b;
e[tot].next=g[a];
g[a]=tot;
}
void dfs(int x)
{
sz[x]=1;
dp[x][1][0]=a[x];
dp[x][0][1]=0;
for(int i=g[x];i;i=e[i].next)
{
dfs(e[i].to);
sz[x]+=sz[e[i].to];
for(int j=sz[x];j>=0;j--)
{
int di=max(0,j-sz[x]+sz[e[i].to]);//上下限都需要剪枝
for(int k=min(j,sz[e[i].to]);k>=di;k--)
{
dp[x][j][0]=min(dp[x][j][0],dp[x][j-k][0]+min(dp[e[i].to][k][0]+a[e[i].to],dp[e[i].to][k][1]));
dp[x][j][1]=min(dp[x][j][1],dp[x][j-k][1]+min(dp[e[i].to][k][0],dp[e[i].to][k][1]));
//cout<<j<<" "<<k<<endl;
}
}
}
}
signed main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dp[i][j][0]=dp[i][j][1]=1e18;
for (int i=1;i<=n;i++)
g[i]=0;tot=0;
for(int i=2;i<=n;i++)
{
int x;scanf("%d",&x);
add(x,i);
}
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(1);
for(int i=n;i>=0;i--)
{
printf("%lld ",min(dp[1][i][0],dp[1][i][1]));
}
puts("");
}
return 0;
}