【2012天津区域赛】部分题解 hdu4431—4441

1001：

题意：

给你13张麻将牌，问可以胡哪些张

思路：

枚举可能接到的牌，然后dfs判断能否胡

 

1002：

题意：

已知n，m 求 n的所有约数在m进制下的平方和

做法：

队长用java高精度写的

代码：

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.io.ObjectInputStream.GetField;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;public class Main {static BigInteger getSum(int i, int base){BigInteger ans= BigInteger.ZERO;BigInteger divider = BigInteger.valueOf(i);String s = divider.toString(base);for (int j = 0; j < s.length(); j++) {BigInteger k = new BigInteger(s.substring(j, j + 1),base);ans = k.multiply(k).add(ans);}return ans;}public static void main(String[] args) {Scanner cin = new Scanner(new BufferedInputStream(System.in));PrintWriter cout = new PrintWriter(new BufferedOutputStream(System.out));while (cin.hasNext()) {int n = cin.nextInt();int base = cin.nextInt();BigInteger ans = BigInteger.ZERO;for (int i = 1; i * i <= n; i++){if (n % i == 0) {// i是dividerans = ans.add(getSum(i, base));if(i*i!=n)ans = ans.add(getSum(n/i, base));}}cout.println(ans.toString(base).toUpperCase());}cin.close();cout.close();}}

 

1003：

题意：

给定一串数，每次有三种操作：

1.把当前数加/减1

2.当前数和后面一个数加/减1

3.当前数和后面两个数加/减1

（加减完后的结果是在0~9循环的）

求把当前状态变到目标状态需要的最小操作数

做法：

处理到每个数的时候最多对后面两个数产生影响，因此十进制最多有 10^2=100 种情况，可以全部存下

可以进行dp，dp[i][j]表示前i个数已经达到目标状态 ，第i+1个数和第i+2个数的被操作情况为j（状压一下）的最小操作数，转移只需要枚举三种操作的次数即可

代码：

#include 
#include 
#include<string.h>
#include
#include<string>
#include
using namespace std;
#define inf 100000
int mod(int x)
{if(x>=0)return x%10;elsereturn (10+x%10)%10;
}
char s[1010];
char to[1010];
int dp[1010][1010];
int num[3];
int tmp[3];
int p[3]= { 1,20,400};
int main()
{while(scanf("%s%s",s+1,to+1)!=EOF){memset(dp,0x3f,sizeof(dp));dp[0][210]=0;int n=strlen(s+1);for(int i=1; i<=n; i++){for(int j=1; j<400; j++){if(dp[i-1][j]>=inf)continue;for(int k=0; k<2; k++){num[k]=(j%p[k+1])/p[k];}int cha=mod(to[i]-s[i]-(num[0]-10));for(int a=0; a<=cha; a++){for(int b=0; a+b<=cha; b++){int c=cha-a-b;tmp[0]=num[1]-10+b+c;tmp[0]=tmp[0]%10+10;tmp[1]=c+10;dp[i][tmp[0]+tmp[1]*20]=min(dp[i][tmp[0]+tmp[1]*20],dp[i-1][j]+cha);}}cha=10-cha;for(int a=0; a<=cha; a++){for(int b=0; a+b<=cha; b++){int c=cha-a-b;tmp[0]=10-(20-num[1]+b+c)%10;tmp[1]=10-c;dp[i][tmp[0]+tmp[1]*20]=min(dp[i][tmp[0]+tmp[1]*20],dp[i-1][j]+cha);}}}}//printf("%d
",dp[1][9+9*20]);//printf("%d
",dp[2][9+10*20]);printf("%d
",dp[n][210]);}return 0;
}

 

1005：

题意：

一个图有n个点，初始在点1，每次加满油后最多能跑d距离，现在点1有一个加油站，问环游全程回到1需要怎么建加油站

第i点建加油站的话 二进制第i位为1，答案要满足建造情况的二进制数最小

做法：

贪心，要尽量要高位的点不建，先假设所有点建了，再从大到小考虑，如果当前点不建也能满足需求，则把该点加油站删去

因为要考虑连通性所以判断是否满足需求要用bfs

代码：

#include 
#include 
#include<string.h>
#include
#include<string>
#include
#include
#include
using namespace std;
int g[150][150];
int x[150];
int y[150];
int vi[150];
int vis[150];
int n,d;
queue<int>q;
int check()
{memset(vis,0,sizeof(vis));while(!q.empty())q.pop();q.push(0);while(!q.empty()){int now=q.front();vis[now]=1;q.pop();for(int i=0;i){if(!vis[i]){if(g[now][i]<=d/2){vis[i]=1;}if(g[now][i]<=d&&vi[i]){q.push(i);}}}}for(int i=0;i){if(vis[i]==0)return 0;}return 1;
}
int main()
{//freopen("in.txt","r",stdin);while(scanf("%d%d",&n,&d)!=EOF){for(int i=0;i){vi[i]=1;}for(int i=0; i){scanf("%d%d",x+i,y+i);}for(int i=0; i){for(int j=0; j){g[i][j]=ceil(sqrt((double)((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))));}}if(check()==0){puts("-1");continue;}for(int i=n-1; i>=1; i--){vi[i]=0;if(!check())vi[i]=1;}int f=1;for(int i=n-1; i>=0; i--){if(vi[i]){printf("1");f=0;}else{if(f==0)printf("0");}}puts("");}return 0;
}

 

1006：

 题意: n个字符串，对于每一个子串可以表示为一个数字， 求所有子串的数字和相加对2012取模，， 相同数字只算一次。

 

这题可以先把n个字符串用一个没有出现过的字符隔开连起来。然后求sa， lcp。

我们可以先看一个简单的例子。

s = 12345

num[1] = 1             sum[1] = 1

num[2] = 12           sum[2] = 1 + 12

num[3] = 123         sum[3] = 1 + 12 + 123

num[4] = 1234       sum[4] = 1 + 12 ＋ 123 + 1234 

num[5] = 12345     sum[5] = 1 + 12 + 123 + 1234 + 12345

如果求[3, 4]  ， 只需要 sum[5] - sum[2] - num[2] * (10 + 100 + 1000)；

判重时 只要从 i+ lcp[rank[i]]  开始算就可以了，，因为公共前缀那一部分 在前面已经算了。

上代码。。

#include <set>
#include 

 

1008：

题意：

很简单的高中数学签到题

思路：

略

代码：

#include <set>
#include 

 

1011：