o(︶︿︶)o 唉跪烂了……
B题由于考虑的不周全WA了3次……
C题由于#include了<cmath>,而我函数声明的是pow(LL a,LL b)但调用的时候 【没!有!把!n!的!数据类型!!改成!long long !!!】所以触发了自动类型转换……就调用成cmath库里的了!!!
教训:
以后自己写函数名的时候尽量避开pow等敏感词(NOIP时候的pipe事件……)可以首字母大写,或者改个名字比如pow_mod
A:
统计题……考你会不会C++(或其他语言……)
统计一下是否26个英文字母都出现了即可,大小写均可。(妈蛋考试的时候Dev-C++突然崩溃了,害我还得重启电脑,没本机跑过一遍不敢交啊……万一CE就是50分QAQ)
//CF #295 div.2 A
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const double eps=1e-;
typedef long long LL;
/*******************template********************/
bool a[];
char s[]; int main(){ int n=getint();
scanf("%s",s);
rep(i,n)
if (s[i]>='A' && s[i]<='Z') a[s[i]-'A']=;
else a[s[i]-'a']=;
bool sign=;
rep(i,)
if (!a[i]) sign=;
puts(sign ? "YES" : "NO");
return ;
}
B:
1.当n>=m时明显*2是无意义的……ans=n-m;
2.当n<m时,一个简单的过程是这样的:n不断翻倍直到n>=m,然后再不断-1直到n==m; 即 $ n*2^{t_1}-1*{t_3} $
那么怎样操作数就减少了呢?在不断$*2$的过程中插入-1操作!也就是说我们的操作可以写成: $ n*2*2\cdots *2 $ 然后又在中间某些位置插入了-1!
那么我们乘法分配律展开一下就变成了 \[ n*2^{t_1} -1*2^{x_1}-1*2^{x_2}-\dots-1*2^{x_n} (其中2^{x_1}+2^{x_2}+ \dots +2^{x_n}=t_3) \]
看上去好像只要将t3进行二进制拆分,相对应的就是一种合法方案了。真的是这样吗?当t3比较大、而t1比较小的时候呢?$2^{x1}$这项前面的系数就不一定是-1了!因为没有更高位可以进位了!
所以应该是用除法!再取余来分解!
//CF #295 div.2 B
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e7+,INF=~0u>>;
const double eps=1e-;
typedef long long LL;
/*******************template********************/
int n,m,ans;
int main(){
n=getint();
m=getint();
ans=;
if (m<=n) ans=n-m;
else {
int t1=;
for(;n<m;n<<=,t1++);
int t2=n-m,t3=;
F(i,,t1) t3<<=;
while(t2){
t1+=t2/t3;
t2%=t3;
t3>>=;
}
ans=t1;
}
printf("%d\n",ans);
return ;
}
C:
sigh……其实是个傻逼题,我被吓到了所以没敢上手……读懂题目意思后很快就解出来了。
从题目描述中给出的样例可以发现:字符串 s 的每一位都要和字符串 t 的每一位匹配 n 次!也就是说其实每一位是单独考虑的……这一位对那个函数 $ \rho(s,t) $ 的贡献取决于这个字符与原串有多少可以匹配的节点!即它与多少位置的字符相同!显而易见如果要找$\rho$最大的,明显需要让 t 中的字符是 s 中出现次数最多的那个,如果有多个最大值(比如A和G都是出现次数最多的),那每一位都会有两种选择,所以总方案数就是 $x^n\mod P$ 其中x为出现次数最多的字符的种数,n为读入的字符串的长度。
//CF #295 div.2 C
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
const int N=1e7+,INF=~0u>>;
const double eps=1e-;
typedef long long LL;
/*******************template********************/
const int P=+;
char s[];
int cnt[];
LL pow(LL a,LL b){
LL r=,base=a;
while(b){
if (b&) r=r*base%P;
base=base*base%P;
b>>=;
}
return r;
}
int main(){
int n;
cin >>n;
scanf("%s",s);
memset(cnt,,sizeof cnt);
rep(i,n){
if (s[i]=='A') cnt[]++;
if (s[i]=='T') cnt[]++;
if (s[i]=='C') cnt[]++;
if (s[i]=='G') cnt[]++;
}
LL max=-,ans=-;
F(i,,){
if (cnt[i]==max) ans++;
else if (cnt[i]>max){ max=cnt[i]; ans=;}
}
LL A=pow(ans,n);
cout << A <<endl;
return ;
}