2017多校联合赛1[题解]

hdu6033-hdu6044

I题调不出来了!!!!

哪位dalao带带我啊.......

(坑估计补不完了.....)

A

题意:输入n,输出2ⁿ-1的位数

思路:log算一下就好..

贴队友代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int n,kase=0;
while(scanf("%d",&n)==1){
printf("Case #%d: %dn",++kase,int(1.0*n*log(2)/log(10)));
}
}

B

题意:给你一堆字符串,每个字母代表一个数字.求你求出所有字符串转化为十进制后的总和的最大值

思路:贪心而已..细节神烦

贴队友代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char buff[100010];
const int mod=1e9+7;
LL ex[100010];
struct bignum{
LL A[100010];
int size;
int id;
bool isfirst;
void init(int x){memset(A,0,sizeof(LL)*(size+1));size=0;id=x;isfirst=0;}
bool operator <(const bignum &x){
if (size!=x.size) return size<x.size;
for (int i=size;i>=0;i--){
if (A[i]!=x.A[i]) return A[i]<x.A[i];
}
return 0;
}
}k[30];
int main(){
int n,kase=0;
ex[0]=1;
for (int i=1;i<=100000;i++) ex[i]=(ex[i-1]*26)%mod;
while(scanf("%d",&n)==1){
for (int i=0;i<30;i++) k[i].init(i);
for (int i=1;i<=n;i++){
scanf("%s",buff);
int len=strlen(buff);
for (int j=len-1,p=0;j>=0;j--,p++){
int pos=buff[j]-'a';
k[pos].A[p]++;
int pp=p;
while (k[pos].A[pp]>25){
k[pos].A[pp++]-=26;
k[pos].A[pp]++;
}
k[pos].size=max(k[pos].size,pp);
if (j==0) k[pos].isfirst=1;
}
}
sort(k,k+26);
int tmp=0;
while(tmp<25&&k[tmp].isfirst) tmp++;
for (int i=tmp;i>0;i--) swap(k[i],k[i-1]);
LL ans=0;
#ifdef waterdragon
for (int i=0;i<26;i++) printf("%c ",k[i].id+'a');
printf("n");
#endif
for (int i=0;i<26;i++){
for (int j=0;j<=k[i].size;j++){
ans=(ans+k[i].A[j]*i*ex[j])%mod;
}
}
printf("Case #%d: %lldn",++kase,ans);
}
}

C:留坑

D:留坑

E:留坑

F

题意:有一种函数,f(x)=y其中0<=x<n,0<=y<m

请你求出一共有多少种方案使得f[x]=b_f(a[x])

思路:向每个x和a[x]连边,发现可以构成一个循环.

然后我们又发现,如果知道f[x]是多少,那么整个循环是否成立也能知道.

然后,设c[x]=a[x]则a[a[x]]=c[c[x]]

发现这样又能构成一个循环..

于是让每个bi向i连一条边,如果有一个a的循环长度是某个b的循环长度的倍数,那么该循环成立

贴自己代码:

#include <cstdio>
#include <cstring>
#define mod 1000000007
#define N 1000010
using namespace std;
typedef long long ll;
ll i,j,k,n,m,x,y,t,T,b[N],c[N],d[N],e,ne[N],v[N],p[N];
void dfs(ll x,ll &y){if (v[x])return;v[x]=1;y++;dfs(ne[x],y);}
int main(){
while (~scanf("%lld%lld",&n,&m)){
memset(v,0,sizeof v);
memset(d,0,sizeof d);
memset(c,0,sizeof c);
memset(p,0,sizeof p);
ll ans=0;
for (i=0;i<n;i++){scanf("%lld",&x);ne[i]=x;}
for (i=0;i<n;i++)if (!v[i]){ans++;dfs(i,d[ans]);}
for (i=0;i<m;i++){scanf("%lld",&b[i]);ne[b[i]]=i;}
memset(v,0,sizeof v);e=0;
for (i=0;i<m;i++){if (v[i])continue;x=0;if (!v[i])dfs(i,x);if (x==1)e++;else for (j=x;j<=n;j+=x)c[j]+=x;}
long long ans1=1;
for (i=1;i<=ans;i++){if (p[d[i]])continue;c[d[i]]+=e;p[d[i]]=1;}
for (i=1;i<=ans;i++)ans1=(ans1*c[d[i]])%mod;
printf("Case #%d: ",++T);printf("%lldn",ans1);
}
return 0;
}

G:留坑

H:

题意:给你一种生成序列的方式,问你该序列第i小是多少

思路:stl题,nth_element简直是神器啊,记得从零开始读入数组..这样更快....

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned uint;
uint A,B,C,n,m,i,j,k,a[10001000],ans[101],x,y,z;
struct data{uint x,id;}b[101];
uint rng61() {
uint t;
x ^= x << 16;
x ^= x >> 5;
x ^= x << 1;
t = x;
x = y;
y = z;
z = t ^ x ^ y;
return z;
}
bool cmp(const data&a,const data&b){return a.x<b.x;}
int main(){
int T=0;
while (~scanf("%u%u%u%u%u",&n,&m,&A,&B,&C)){
x = A, y = B, z = C;
for (i=0;i<m;i++){scanf("%u",&b[i].x);b[i].id=i;}
sort(b,b+m,cmp);
for (i=0;i<n;i++)a[i]=rng61();
b[m].x=n;
for (i=m-1;~i;i--){nth_element(a,a+b[i].x,a+b[i+1].x);ans[b[i].id]=a[b[i].x];}
printf("Case #%d:",++T);for (i=0;i<m;++i)printf(" %u",ans[i]);printf("n");
}
return 0;
}

I:留坑

J:留坑

K:

题意:输入一个n和一个k,每天选一个可以用的最小的数,并将该数扔到一个垃圾堆里..当垃圾堆里有n-1个数时..就将这些数重新排序再放回去.问第k次你取出的是哪个数.

思路:先找规律找出循环节,再分类讨论.

贴我的代码:

#include <cstdio>
using namespace std;
int T;
long long n,m;
int main(){
while (~scanf("%lld%lld",&n,&m)){
printf("Case #%d: ",++T);
if (m<=n){printf("%lldn",m);continue;}
long long t=(m-n)%(n-1+n-2+1);
if (t==0)t=(n-1+n-2+1);
if(t<=n-1)printf("%lldn",t);
else if (t==(n-1+n-2+1))printf("%lldn",n);
else printf("%lldn",t-(n-1));
}
return 0;
}

l:留坑