A 工具人和小D
来源：51nod 2336
题意：在一棵树上割一个连通块，使内部不同颜色的节点数目差的绝对值最大。
树形dp水题了，看数据1e5容易推测出可能是dp[100005][2]的做法。然后就往这方面想。dp[i][0]代表白色的节点较多时差的最大值，dp[i][1]代表黑色的节点较多时差的最大值，思考怎么转移就好了，对于子树j，如果dp[j][0]>0那么就把他加入到dp[i][0]里，dp[j][1]同理；对于每个节点，假设颜色为c，初始化就是dp[i][c]=1,dp[i][1-c]=0。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
vector<int> g[maxn];
int c[maxn],dp[maxn][2];
void dfs(int x,int fa){
dp[x][c[x]]=1;
dp[x][1-c[x]]=-1;
int l=0,r=0;
for(auto i:g[x]){
if(i!=fa){
dfs(i,x);
if(dp[i][0]>0)l+=dp[i][0];
if(dp[i][1]>0)r+=dp[i][1];
}
}
dp[x][0]+=l;
dp[x][1]+=r;
}
signed main()
{
IOS
int n;
cin>>n;
for (int i = 1; i <=n ; ++i) {
cin>>c[i];
}
for (int j = 0; j <n-1 ; ++j) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,-1);
int ma=-1;
for (int k = 1; k <=n ; ++k) {
ma=max(ma,max(dp[k][0],dp[k][1]));
}
cout<<ma;
return 0;
}
B 工具人的BTS
来源：HDU 1124
题意：求n!末尾有几个0.
显然n!末尾的零是由2×5得到的，每对2×5贡献一个0，那么只需要找5和2中个数最小的一个就好，显然5的较小。而5的个数就是1~n中5的倍数的个数+25的倍数的个数……先求5的倍数的个数，即n/5，考虑全部缩小为原来的1/5，令n/5，那么原来时25倍数的数现在就是5的倍数，同理求出其他倍数即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 5005
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
signed main()
{
IOS
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll ans=0;
while(n){
ans+=n/5;
n/=5;
}
cout<<ans<<endl;
}
return 0;
}
C 工具人的卡片
来源：HDU 4336
题意：每一包小浣熊有概率开出卡片，也可能开不出，不同卡片有各自的爆率，问得到所有卡片的期望次数。
看眼数据范围，大致就能想到状压记录取得情况了，不妨令dp[i]代表状态为i时到达终点状态的期望次数，然后从终点状态倒推即可。
对于每包可能有如下情况：
1、老非酋了，状态不变
2、开出已经有的，状态不变
3、开出还没有的，状态变化
第一种情况即为dp[i]=p0*(dp[i]+1)
第二种情况即为dp[i]=p1*(dp[i]+1)，p1为已经拥有的卡片概率之和
第三种情况即为dp[i]=Σpj*(dp[j]+1)，j即为获得之后的状态
每次转移都是多买了一包，所以需要＋1，之后把dp[i]移到一边计算即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 25
#define ld double
ld p[maxn],dp[(1<<21)-1];
#define eps 1e-4
#pragma GCC optimize(2)
signed main()
{
int n;
while(~scanf("%d",&n)){
ld africa=1.0;
for (int i = 1; i <=n ; ++i) {
scanf("%lf",&p[i]);
africa-=p[i];
}
memset(dp,0,sizeof(dp));
for (ll j = (1<<n)-2; j >=0 ; --j) {
ld p1=0.0,p2=0.0;
for (int i = 1; i <=n ; ++i) {
if(j&1<<(i-1))p1+=p[i];
else p2+=p[i]*(dp[j|(1<<(i-1))]+1);
}
p1+=africa;
dp[j]=(p1+p2)/(1-p1);
}
printf("%.4f
",dp[0]);
}
return 0;
}
D 工具人的签到题
来源：Codeforces 1287A
题意：每轮每个生气的人会向下一个人扔雪球使他变生气，问最后有学生变生气的时刻。
贪心一下，找左边有A的最长连续P串的长度就好了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
signed main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string a;
cin>>a;
int fl=0,ans=0,len=a.size();
for (int i = 0; i < len; ++i) {
if(a[i]=='A')fl=1;
else{
if(fl==1){
int tmp=0;
while(a[i]!='A'&&i<len){i++;tmp++;}
ans=max(ans,tmp);
}
}
}
cout<<ans<<endl;
}
return 0;
}
E 加密工具人
来源：HDU 1211
题意：求一个逆元+快速幂
这道题看起来挺麻烦，其实是一道板子题，把多余信息筛掉之后，就是扩欧求一个逆元，然后一个快速幂求出答案即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 505
#define int long long
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
int x,y,p,q,e,l,n,f;
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b){ d=a; x=1; y=0;}
else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll guisu_pow(ll a,ll power,ll mod){
ll ans=1;
while(power){
if(power&1)ans=ans*a%mod;
a=a*a%mod;
power>>=1;
}
return ans;
}
signed main()
{
while(cin>>p>>q>>e>>l){
n=p*q,f=(p-1)*(q-1);
ll d;
extgcd(e,f,d,x,y);
x=(x%f+f)%f;
while(l--){
ll code;
cin>>code;
ll t=guisu_pow(code,x,n);
printf("%c",t);
}
cout<<'
';
}
return 0;
}
F 工具人的字符串
来源：HDU 2476
题意：每次可以把a串中任意一段刷成一样的字母，问多少次后可以把a变成b
看数据范围应该是开个多维的dp，考虑到a只有在相同位置字符一样时对结果产生影响，那就可以开个二维的dp记录刷i到j的最小代价，之后转移即可。
显然dp[i][j]最大值为j-i+1，即每个都单独刷，思考转移，如果第i个和第k个一样，那么刷第k个的时候可以顺带刷了i，那么有：
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
但是每次转移的时候都需要用到左端点之后的，那么考虑每次固定右端点，然后左端点不断左移去更新。
for (int i = 0; i < len; ++i) {
for (int j = i; j >=0 ; --j) {
dp[j][i]=dp[j+1][i]+1;
for (int k = j+1; k <=i ; ++k) {
if(b[j]==b[k]){
dp[j][i]=min(dp[j][i],dp[j+1][k]+dp[k+1][i]);
}
}
}
}
但是这种转移只是考虑了b串，现在加入a串考虑。
可以加入另一个数组记录前i个字符的最小代价，如果字符相同，就有ans[i]=ans[i-1]，否则就尝试最小化当前的ans值，找出最优的分割点，即
if(a[m]!=b[m]){
for (int i = 0; i <m ; ++i) {
ans[m]=min(ans[m],ans[i]+dp[i+1][m]);
}
}
全部代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 105
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
int dp[maxn][maxn],ans[maxn];
char a[maxn],b[maxn];
signed main()
{
IOS
while(cin>>a>>b){
int pos=0,len=strlen(a);
memset(dp,0, sizeof(dp));
for (int i = 0; i < len; ++i) {
for (int j = i; j >=0 ; --j) {
dp[j][i]=dp[j+1][i]+1;
for (int k = j+1; k <=i ; ++k) {
if(b[j]==b[k]){
dp[j][i]=min(dp[j][i],dp[j+1][k]+dp[k+1][i]);
}
}
}
}
for (int l = 0; l <len ; ++l) {
ans[l]=dp[0][l];
}
for (int m = 0; m <len ; ++m) {
if(a[m]!=b[m]){
for (int i = 0; i <m ; ++i) {
ans[m]=min(ans[m],ans[i]+dp[i+1][m]);
}
}else{
if(m>0)ans[m]=ans[m-1];
else ans[m]=0;
}
}
cout<<ans[len-1]<<endl;
}
return 0;
}
G 工具人的数对
来源：HDU 1394
题意：每次将数列的第一个放到末尾，求过程中逆序对数的最小值。
暴力
数据范围只有5000，第一种做法是直接n^2暴力。
对于a[0]，由于数列刚好是0~n-1的排列，那么a[0]如果移动至末尾，会增加n-1-a[0]，减少a[0]个，那么先求出初始逆序对，O(n)找最小值即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 5005
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
int n;
int a[maxn];
signed main()
{
IOS
while(cin>>n){
for (int i = 1; i <=n ; ++i) {
cin>>a[i];
}
int cnt=0;
int ans=100000000;
for (int j = 1; j <n ; ++j) {
for (int i = j+1; i <=n ; ++i) {
if(a[i]<a[j]){
cnt++;
}
}
}
ans=cnt;
for (int k = 1; k <n ; ++k) {
cnt+=n-1-a[k];
cnt-=a[k];
ans=min(ans,cnt);
}
cout<<ans<<endl;
}
return 0;
}
树状数组
优化就是用树状数组求逆序对数，每个a出现，次数就加一，然后统计比a大的有多少个1，最后相加就是逆序对数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 5005
#define int long long
#define eps 1e-4
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define lowbit(x) ((x)&-(x))
int c[maxn],a[maxn];
int n;
void update(int x,int v){
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=v;
}
}
int getsum(int x){
int sum = 0;
for(int i=x;i>=1;i-=lowbit(i)){
sum+=c[i];
}
return sum;
}
signed main()
{
IOS
while(cin>>n){
for (int i = 1; i <=n ; ++i) {
cin>>a[i];
a[i]++;
}
memset(c,0, sizeof(c));
int cnt=0;
for (int j = 1; j <=n ; ++j) {
update(a[j],1);
cnt+=j-getsum(a[j]);
}
int ans=cnt;
for (int k = 1; k <=n ; ++k) {
cnt = cnt+(n-a[k])-(a[k]-1);
ans=min(ans,cnt);
}
cout<<ans<<endl;
}
return 0;
}