1001 Add More Zero（签到题）
题目链接 HDU6033 Add More Zero
#include <cstdio>
#include <cmath>
int cas,m;
int main(){
while(~scanf("%d",&m)){
printf("Case #%d: %dn", cas,(int)(m*log(2)/log(10)));
}
return 0;
}1002 Balala Power!（贪心）
题目链接 HDU6034 Balala Power!
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100005
#define M 26
using namespace std;
typedef long long ll;
const ll MOD=(1e9 7);
struct Node{
int id;
int big;
bool zero;
}zm[M];
ll p[N];
ll k[M][N];
char s[N];
int cas,n;
void init(){
p[0]=1;
for(int i=1;i<N; i)p[i]=p[i-1]*M%MOD;
}
bool cmp(const Node& a,const Node& b){
if(a.big==b.big){
int i;
for(i=a.big;i&&k[a.id][i]==k[b.id][i];--i);
return k[a.id][i]<k[b.id][i];
}
return a.big<b.big;
}
ll solve(){
for(int i=0;i<M; i){
for(int j=0;j<=zm[i].big; j){
if(k[i][j]>=M){
k[i][j 1] =k[i][j]/M;
k[i][j]%=M;
if(j==zm[i].big) zm[i].big;//！！！
}
}
}
sort(zm,zm M,cmp);
ll ans=0;
int i;
for(i=0;i<M&&!zm[i].zero; i);
rotate(zm,zm i,zm i 1);
for(int i=0;i<M; i){
for(int j=0;j<=zm[i].big; j){
ans =k[zm[i].id][j]*p[j]*i;
if(ans>=MOD)ans%=MOD;
}
}
return ans;
}
int main(){
init();
while(~scanf("%d",&n)){
for(int i=0;i<M; i){
zm[i].id=i;
zm[i].big=0;
zm[i].zero=true;
memset(k[i],0,sizeof(k[i]));
}
for(int i=0;i<n; i){
scanf("%s",s);
int len=strlen(s);
if(len>1)zm[s[0]-'a'].zero=false;
for(int j=0;s[j]; j){
int d=s[j]-'a';
k[d][len-j-1];
zm[d].big=max(zm[d].big,len-j-1);
}
}
printf("Case #%d: %lldn", cas,solve());
}
return 0;
}1003 Colorful Tree（dfs）
题目链接 HDU6035 Colorful Tree
我参考的题解
代码语言：javascript复制#include <bits/stdc .h>
#define N 200001
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
int n;
vector<int> e[N];
int siz[N];
int col[N];
ll sum[N];
ll ans;
void dfs(int u,int f){
siz[u]=1;
ll tot=0;
for(auto v:e[u]){
if(v!=f){
ll prev = sum[col[u]];
dfs(v,u);
siz[u] = siz[v];
ll sumv = sum[col[u]] - prev;
ll othr = siz[v] - sumv;
tot = sumv;
ans -= (othr-1)*othr/2;
}
}
sum[col[u]] =siz[u]-tot;
}
int cas;
int cnt;
bool mark[N];
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n; i){
e[i].clear();
mark[i]=0;
sum[i]=0;
cnt=0;
}
for(int i=1;i<=n; i){
scanf("%d",&col[i]);
if(!mark[col[i]]){
mark[col[i]]=1;
cnt;
}
}
for(int i=1;i<n; i){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
e[v].pb(u);
}
ans=(ll)n*(n-1)/2*cnt;
dfs(1,0);
for(int i=1;i<=n; i)
if(sum[i]){
ll up=n-sum[i];
ans-=(up-1)*up/2;
}
printf("Case #%d: %lldn", cas,ans);
}
return 0;
}1006 Function（置换）
题目链接 HDU6038 Function
#include <cstdio>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define N 100001
typedef long long ll;
const ll MOD =1e9 7;
int n,m,cas;
int a[N],b[N],len[N];
bool vis[N];
int main() {
int n,m;
while(~scanf("%d%d",&n,&m)) {
mem(len,0);
mem(vis,0);
for(int i=0; i<n; i)
scanf("%d",a i);
for(int j=0; j<m; j)
scanf("%d",b j);
for(int i=0; i<m; i)
if(!vis[i]) {
int t=b[i];
int l=1;
while(t!=i) {
vis[t]=true;//！！
t=b[t];
l;
}
len[l];
}
mem(vis,0);
ll ans=1;
for(int i=0; i<n; i)
if(!vis[i]) {
int t=a[i];
int l=1;
while(t!=i) {
vis[t]=true;
t=a[t];
l;
}
ll res=0;
for(int j=1; j*j<=l; j)
if(l%j==0) {
if(j*j!=l) res =(ll)l/j*len[l/j];//！！！
res =(ll)j*len[j];
res%=MOD;
}
ans=ans*res%MOD;
}
printf("Case #%d: %lldn", cas,ans);
}
return 0;
}1011 KazaQ‘s Socks（找规律）
题目链接 HDU6043 KazaQ‘s Socks
#include <cstdio>
long long n,k;
int t;
int main(){
while(~scanf("%lld%lld",&n,&k)){
printf("Case #%d: ", t);
if(k<=n)printf("%lldn",k);
else{
k-=n;
if(k%(n-1))
printf("%lldn",k%(n-1));
else if((k/(n-1))%2)
printf("%lldn",n-1);
else
printf("%lldn",n);
}
}
return 0;
}1012 Limited Permutation（递归）
题目链接 HDU6044 Limited Permutation
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cctype>
#include <map>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1000001;
const LL MOD =1e9 7;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
return p1==p2&&(p2=(p1=buf) fread(buf,1,100000,stdin),p1==p2)?EOF:*p1 ;
}
inline bool rea(int & x){
char c=nc();x=0;
if(c==EOF) return false;
for(;!isdigit(c);c=nc());
for(;isdigit(c);x=x*10 c-'0',c=nc());
return true;
}
inline bool rea(LL & x){
char c=nc();x=0;
if(c==EOF) return false;
for(;!isdigit(c);c=nc());
for(;isdigit(c);x=x*10 c-'0',c=nc());
return true;
}
int cas;
int n;
int l[N];
map<PII,int> mm;
LL fac[N],inv[N];
LL qpow(LL a,LL b){
LL ans=1;
while(b){
if(b&1)ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans;
}
void init(){
fac[0] = inv[0] =1;
for(int i=1;i<N; i){
fac[i]=fac[i-1]*i%MOD;
inv[i]=qpow(fac[i],MOD-2);
}
}
LL C(LL n,LL m){
return n<m?0:(fac[n]*inv[m]%MOD)*inv[n-m]%MOD;
}
LL solve(int l,int r){
if(l>r 1)return 0;
if(l==r 1)return 1;
auto it=mm.find(mp(l,r));
if(it==mm.end()){
return 0;
}
int x=it->second;
if(x<l||x>r)return 0;
if(l==r)return 1;
LL ans=solve(l,x-1)*solve(x 1,r)%MOD*C(r-l, x-l)%MOD;
return ans;
}
int main(){
init();
while(rea(n)){
mm.erase(mm.begin(),mm.end());
for(int i=1;i<=n; i){
rea(l[i]);
}
for(int i=1;i<=n; i){
int r;
rea(r);
mm[mp(l[i],r)]=i;
}
printf("Case #%d: %lldn", cas,solve(1,n));
}
return 0;
}
