題目:https://vjudge.net/contest/185485
A
#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
#include <climits>
int main(){
int score[100000];
int n1,n2,inpu,max,ans;
char a[100];
scanf("%d",&n1);
while(n1--){
scanf("%d",&n2);
memset(score,0,sizeof(score));
max=INT_MIN;
while(n2--){
//printf("hi\n");
scanf("%s %d",a,&inpu);
score[inpu]++;
//printf("%s\n",a);
}
for(int i=0;i<100000;i++){
if(score[i]>max){
max=score[i];
ans=i;
}
}
printf("%d\n",ans);
}
return 0;
}
B
#include <stdio.h>
#include <string.h>
int main(){
int n1,ans,tem;
char a[100007],b[100007],c;
int coub[26];
scanf("%d",&n1);
while(n1--){
ans=0,tem=0;
memset(coub,0,sizeof(coub));
scanf("%s %s",a,b);
int index=0;
for(int i=0;i<strlen(b);i++)
coub[b[i]-'a']++;
for(int i=0;i<strlen(a);i++){
if(coub[a[i]-'a']==0) break;
coub[a[i]-'a']--;
ans++;
}
printf("%d\n",ans);
}
return 0;
}
會ＴＬＥ
改成
#include <stdio.h>
#include <string.h>
int main(){
int n1,ans,tem;
char a[100007],b[100007],c;
int coub[26];
scanf("%d",&n1);
while(n1--){
ans=0,tem=0;
memset(coub,0,sizeof(coub));
scanf("%s %s",a,b);
int index=0;
for(int i=0;b[i]!=0;i++)
coub[b[i]-'a']++;
for(int i=0;a[i]!=0;i++){
if(coub[a[i]-'a']==0) break;
coub[a[i]-'a']--;
ans++;
}
printf("%d\n",ans);
}
return 0;
}
其實就是for迴圈，判斷上限的方法改變而已。
結論：strlen很慢
C
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <climits>
int main(){
int n,a[3];
scanf("%d",&n);
while(n--){
int i;
int ans,min=INT_MAX;
for(i=0;i<3;i++)
scanf("%d",&a[i]);
for(i=0;i<3;i++)
if(a[i]<min){
min=a[i];
ans=i;
}
if(ans==0)
printf("First\n");
else if(ans==1)
printf("Second\n");
else if(ans==2)
printf("Third\n");
}
return 0;
}
D
原理可以看離散數學，費曼小定理(考研的書剛好有)。
利用陣列儲存階乘，再用fast power取模逆元，利用上面兩個東西，算出大數組合數取質數模。(費曼小定理不一定只能算質數模，詳情可以查一下。)
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010
typedef long long LL;
int p=1e9+7;
LL fra[100005];
LL Pow(LL a,LL b,LL mod)
{
LL ans=1;
while(b)
{
if(b&1)
{
b--;
ans=(ans*a)%mod;
}
else
{
b/=2;
a=(a*a)%mod;
}
}
return ans;
}
LL C(LL n,LL m)
{
if(n<m)
return 0;
LL ans=1;
/*for(int i=1;i<=m;i++)
{
ans=ans*(((n-m+i)%p)*Pow(i,p-2,p)%p)%p;
} */
return fra[n]*Pow(fra[m],p-2,p)%p*Pow(fra[n-m],p-2,p)%p;
}
LL Lucas(LL n,LL m)
{
if(m==0)
return 1;
return (Lucas(n/p,m/p)*C(n%p,m%p))%p;
}
int main()
{
int t;
LL n,m;
scanf("%d",&t);
fra[0]=1;
for(int i=1;i<100005;i++){
fra[i]=fra[i-1]*i%p;
}
while(t--)
{
scanf("%lld%lld",&n,&m);
//printf("%lld\n",Lucas(n-1,m)*2);
printf("%lld\n",2*C(n-1,m)%p);
}
return 0;
}
有空的話，可以檢查一下lucas為什麼會出錯。
用LUCAS就會一直跳ERROR
組合+取模+取模反元素
找到錯誤了
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010
typedef long long LL;
int p=1e9+7;
LL fra[100005];
LL Pow(LL a,LL b,LL mod)
{
LL ans=1;
while(b)
{
if(b&1)
{
b--;
ans=(ans*a)%mod;
}
else
{
b/=2;
a=(a*a)%mod;
}
}
return ans;
}
LL C(LL n,LL m)
{
if(n<m)
return 0;
LL ans=1;
/*for(int i=1;i<=m;i++)
{
ans=ans*(((n-m+i)%p)*Pow(i,p-2,p)%p)%p;
} */
return fra[n]*Pow(fra[m],p-2,p)%p*Pow(fra[n-m],p-2,p)%p;
}
LL Lucas(LL n,LL m)
{
if(m==0)
//return 0;
return 1;
return (Lucas(n/p,m/p)*C(n%p,m%p))%p;
}
int main()
{
int t;
LL n,m;
scanf("%d",&t);
fra[0]=1;
for(int i=1;i<100005;i++){
fra[i]=fra[i-1]*i%p;
}
while(t--)
{
scanf("%lld%lld",&n,&m);
printf("%lld\n",2*Lucas(n-1,m)%p);
//printf("%lld\n",2*C(n-1,m)%p);
}
return 0;
}
E
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <climits>
int main(){
int n,a,b;
scanf("%d",&n);
while(n--){
scanf("%d %d",&a,&b);
printf("%d\n",a+b-1);
}
return 0;
}
F
G
http://blog.csdn.net/lyg_air/article/details/77645433
我一開始的寫法，沒有判斷上下限，於是會TLE
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
LL lcm(LL a,LL b){
LL res=(a/__gcd(a,b))*b;
return res;
}
int main(){
int n,k;
LL a[2003];
scanf("%d",&n);
while(n--){
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%lld",&a[i]);
}
int ans=0;
for(int i=0;i<k;i++){
LL nowlcm=1;
LL sum=0;
for(int j=i;j<k;j++){
nowlcm=lcm(a[j],nowlcm);
sum+=a[j];
if(sum%nowlcm==0)
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
最後開抄，看別人的解答，發覺可以判斷lcm有沒有超過總合的最大上限(2000*1E9，因為最多就2000個數字，並且每個數字的最大上限是1E9)，來加速。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
LL lcm(LL a,LL b){
LL res=(a/__gcd(a,b))*b;
if(res>(2000*1e9)){
return -1;
}
return res;
}
int main(){
int n,k;
LL a[2003];
scanf("%d",&n);
while(n--){
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%lld",&a[i]);
}
int ans=0;
for(int i=0;i<k;i++){
LL nowlcm=1;
LL sum=0;
for(int j=i;j<k;j++){
nowlcm=lcm(a[j],nowlcm);
if(nowlcm==-1) break;
sum+=a[j];
if(sum%nowlcm==0)
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
就過了。
但還是想問問宇航是怎麼檢查的，我看不懂qq。
H
在virtual judge裡，陣列大小取錯，好像也會TLE
原本眼殘，陣列只開10萬，瘋狂TLE。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <string.h>
#define min(x,y) ((x)<(y)?(x):y)
using namespace std;
int main(){
int n1,n2,n3,as[1000003],tem;
scanf("%d",&n1);
while(n1--){
scanf("%d %d",&n2,&n3);
if((n2>=2 && n3==1) || n2*9<n3){
printf("-1\n");
}else if(n2>=2 && n3==1){
printf("-1\n");
}else if(n2%2==0){
if(n3%2==1){
printf("-1\n");
}
else{
n3/=2;
for(int i=0;i<n2/2;i++){
tem=min(n3,9);
printf("%d",tem);
as[i]=tem;
n3-=tem;
}
reverse(as,as+n2/2);
for(int i=0;i<n2/2;i++)
printf("%d",as[i]);
printf("\n");
}
}else if(n2%2!=0){
for(int i=0;i<n2/2;i++){
tem=min(n3/2,9);
printf("%d",tem);
as[i]=tem;
n3-=tem*2;
}
printf("%d",n3);
reverse(as,as+n2/2);
for(int i=0;i<n2/2;i++)
printf("%d",as[i]);
printf("\n");
}
}
return 0;
}
I
J
K
搞懂dp在幹嘛了
再來看dp2在幹嘛
http://blog.csdn.net/qq_18869763/article/details/77621623
http://blog.csdn.net/lifelikes/article/details/77644347
L
我：Bellmon，有重複路徑的話，紀錄比較小的那個。
M