1001 Add More Zero
hdoj6033题目链接
2^n在减了1之后位数是不会改变的
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t=0,n;
while(~scanf("%d",&n)) printf("Case #%d: %d\n",++t,int(log10(2.0)*n));
}1002 Balala Power!
hdoj6034题目链接
将每一个字母对答案的贡献处理成一个26进制数，这个数字越大则给该字母分配越大的数，这样便能贪心得到最大的和
要注意不能有前导零，所以要保证最小的权值0是分配给一个没有在长度大于1的串的首位出现过的字母，详见代码
” It is guaranteed that at least one character does not appear at the beginning of any string.”保证是有解的
//代码中结构体里的a数组是动态清零的，看起来稍稍复杂一丢丢，直接memset也阔以
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 100005
const LL M=1e9+7;
LL pn[N],ans,s[30];
struct node
{
int id,len;
LL a[N]; //字母序号；26进制数的长度；下标为0表示最低位
}p[30];
bool cmp(const node& x,const node& y) //按26进制数从小到大排序
{
if(x.len!=y.len) return x.len<y.len;
for(int i=x.len-1;~i;i--)if(x.a[i]!=y.a[i]) return x.a[i]<y.a[i];
return 0; //务必要加上这一句，不然程序都跑不出来
}
int main()
{
int t=0,n,vs[30],i,j,l,tmp;
char ss[N];
for(pn[0]=i=1;i<N;i++) pn[i]=pn[i-1]*26%M; //预处理位权
while(~scanf("%d",&n)){
for(i=0;i<26;i++) vs[i]=0,p[i].id=i,p[i].len=0;
while(n--){
scanf("%s",ss);
l=strlen(ss);
if(l!=1) vs[ss[0]-'a']=1; //长度不为1的串的首位字母打上标记(其分配数不能是0)
for(i=1;i<=l;i++){ //倒着处理，因为结构体中的a数组下标为0表示最低位
tmp=ss[l-i]-'a';
while(p[tmp].len<i) p[tmp].a[p[tmp].len++]=0;
p[tmp].a[i-1]++;
}
}
for(i=0;i<26;i++)for(j=0;j<p[i].len;j++)if(p[i].a[j]>=26){ //处理26进制数的进位
if(j==p[i].len-1) p[i].a[p[i].len++]=0;
p[i].a[j+1]+=p[i].a[j]/26,p[i].a[j]%=26;
}
sort(p,p+26,cmp);
for(i=0;i<26;i++) s[p[i].id]=i; //初次分配(贪心策略)
for(i=0;vs[p[i].id];i++) swap(s[p[i].id],s[p[i+1].id]); //再分配(保证不出现前导零的情况)
for(ans=i=0;i<26;i++)for(j=0;j<p[i].len;j++) ans=(ans+s[p[i].id]*p[i].a[j]%M*pn[j]%M)%M;
printf("Case #%d: %lld\n",++t,ans);
}
}1003 Colorful Tree
hdoj6035题目链接
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 200005
vector<int>E[N];
int t,c[N],sz[N],sum[N],x,y,i;
LL n,ans,num;
void dfs(int u,int f)
{
sz[u]=1;
int pre=sum[c[u]],tot=0;
for(int v:E[u])if(v!=f){
dfs(v,u);
sz[u]+=sz[v];
int same=sum[c[u]]-pre;
tot+=same;
LL none=sz[v]-same;
ans+=none*(none-1)/2;
pre=sum[c[u]];
}
sum[c[u]]+=sz[u]-tot;
}
int main()
{
while(~scanf("%lld",&n)){
for(i=1;i<=n;i++) scanf("%d",&c[i]),E[i].clear();
for(i=1;i<n;i++) scanf("%d%d",&x,&y),E[x].push_back(y),E[y].push_back(x);
memset(sum,0,sizeof(sum));
ans=num=0;
dfs(1,0);
for(i=1;i<=n;i++)if(sum[i]){
LL none=sz[1]-sum[i];
ans+=none*(none-1)/2;
num++;
}
printf("Case #%d: %lld\n",++t,n*(n-1)/2*num-ans);
}
}1006 Function
hdoj6038题目链接
#include<bits/stdc++.h>
using namespace std;
#define ms(x) memset(x,0,sizeof(x))
typedef long long LL;
const int N=1e5+5;
const int M=1e9+7;
bool vs[N];
LL a[N],b[N],sz[N],ans,tmp;
int main()
{
int t=0,n,m,i,j,p,q;
while(~scanf("%d%d",&n,&m)){
for(i=0;i<n;i++) scanf("%d",&a[i]);
for(i=0;i<m;i++) scanf("%d",&b[i]);
ms(vs),ms(sz);
for(i=0;i<m;i++)if(!vs[i]){
p=i,q=0;
while(!vs[p]) vs[p]=1,q++,p=b[p];
sz[q]++;
}
for(ms(vs),ans=1,i=0;i<n;i++)if(!vs[i]){
p=i,q=0;
while(!vs[p]) vs[p]=1,q++,p=a[p];
p=sqrt(1.0*q);
for(tmp=0,j=1;j<=p;j++)if(q%j==0){
tmp=(tmp+j*sz[j]%M)%M;
if(j*j!=q) tmp=(tmp+q/j*sz[q/j]%M)%M;
}
ans=ans*tmp%M;
}
printf("Case #%d: %lld\n",++t,ans);
}
}1008 Hints of sd0061
hdoj6040题目链接
#include<bits/stdc++.h>
using namespace std;
typedef unsigned U;
struct node
{
int id,v;
U s;
}b[105];
bool cmp1(const node& p,const node& q) { return p.v<q.v; }
bool cmp2(const node& p,const node& q) { return p.id<q.id; }
int c,n,m,i,tmp;
U x,y,z,a[10000005];
U rng61() {
U t;
x ^= x << 16;
x ^= x >> 5;
x ^= x << 1;
t = x;
x = y;
y = z;
z = t ^ x ^ y;
return z;
}
int main()
{
while(~scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)){
for(i=1;i<=m;i++) scanf("%d",&b[i].v),b[i].v++,b[i].id=i;
for(i=1;i<=n;i++) a[i]=rng61();
sort(b+1,b+1+m,cmp1);
tmp=n;
for(i=m;i;i--)
if(i<m&&b[i].v==b[i+1].v) b[i].s=b[i+1].s;
else nth_element(a+1,a+b[i].v,a+1+tmp),b[i].s=a[b[i].v],tmp=b[i].v;
sort(b+1,b+1+m,cmp2);
printf("Case #%d: ",++c);
for(i=1;i<m;i++) printf("%u ",b[i].s);
printf("%u\n",b[i].s);
}
}1011 KazaQ’s Socks
hdoj6043题目链接
简单规律：1,2,…,n-2,n-1,n；
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL t=0,n,k,p,q,s;
while(~scanf("%lld%lld",&n,&k)){
if(k<=n) s=k;
else{
k-=n;
p=k/(n-1);
q=k%(n-1);
if(q) s=q;
else s=p%2?n-1:n;
}
printf("Case #%lld: %lld\n",++t,s);
}
}