新竹高中軟體研究社: 社博歡樂題

題目、測資、標程 https://www.dropbox.com/s/82881ybrgh4e23h/%E7%A4%BE%E5%8D%9A%E6%AD%A1%E6%A8%82%E9%A1%8C.rar

pA a+b問題

解法 : 兩個數相加起來

#include<stdio.h>
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",a+b);
}

pB 明明的隨機數 (NOIP 2006 普及組)

解法 : Sort

#include<stdio.h>
#include<map>
using namespace std;
map<int,int> ma;
map<int,int>::iterator k;
int main(){
    int n,m,i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&m);
        ma[m]=1;
    }
    printf("%d\n",ma.size());
    for(k=ma.begin();k!=ma.end();k++){
        printf("%d ",k->first);
    }
    puts("");
}

pC 開心的金明 (NOIP 2006 普及組)

解法 : DP

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[30005]={0};
int c[30],p[30];
int main(){
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&c[i],&p[i]);
        p[i]*=c[i];
        for(j=n;j>=c[i];j--)
            if(dp[j-c[i]]+p[i]>dp[j])
                dp[j]=dp[j-c[i]]+p[i];
    }
    printf("%d\n",dp[n]);
}

pD 水之都 (NPSC 2006 國中組初賽)

解法 : Dijkstra

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
struct P{
    int r,w;
};
vector<P> vec[1005];
int d[1005],v[1005];
int main(){
    int t,i,j,n,m,ans,x,y,a,b,c,big,l;
    while(scanf("%d%d",&n,&m)!=EOF && n+m){
        for(i=1;i<=n;i++)
            vec[i].clear();
        memset(v,0,sizeof(v));
        memset(d,0,sizeof(d));
        for(i=0;i<m;i++){
            scanf("%d%d%d",&a,&b,&c);
            vec[a].push_back((P){b,c});
            vec[b].push_back((P){a,c});
        }
        scanf("%d%d",&x,&y);
        d[x]=999999999;
        for(i=1;i<=n;i++){
            big=0;
            for(j=1;j<=n;j++){
                if(!v[j] && d[j]>big)
                    big=d[j],l=j;
            }
            v[l]=1;
            for(j=0;j<vec[l].size();j++){
                d[vec[l][j].r]=max(d[vec[l][j].r],min(d[l],vec[l][j].w));
            }
        }
        printf("%d\n",d[y]);
    }
}

pE 電梯向上 (NPSC 2012 高中組初賽)

解法 : Binary Search

#include<stdio.h>
#include<string.h>
int s[100005];
int main(){
    int i,j,t,n,m,x,y,l,r,mi,add,num;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(i=l=0;i<n;i++){
            scanf("%d%d",&x,&y);
            s[x]=y;
            if(y>l) l=y;
        }
        r=100005;
        while(r!=l+1){
            mi=(l+r)/2;
            add=0,num=1;
            for(i=0;i<n;i++){
                if(add+s[i]<mi) add+=s[i];
                else{
                    num++;
                    add=s[i];
                }
            }
            if(num<=m) r=mi;
            else l=mi;
        }
        printf("%d\n",l);
    }
}

pF 蚯蚓的遺跡保衛戰2 (NPSC 2012 高中組決賽)

解法 : Greedy

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct T{
 int C,B;
 friend bool operator <(T a,T b){
     if(a.B*b.C!=b.B*a.C)
            return a.B*b.C>b.B*a.C;
  else
            return a.B<b.B;
 }
}in;
long long int gcd(long long int a,long long int b){
    if(b%a==0) return a;
    return gcd(b%a,a);
}
long long int ans,now,ans2;
vector<T> vec;
vector<T>::iterator i;
int main(){
 int t,n;
 scanf("%d",&t);
 while(t--){
  scanf("%d",&n);
  while(n--){
   scanf("%d%d",&in.C,&in.B);
   vec.push_back(in);
  }
  ans=0,now=1,ans2=0;
  sort(vec.begin(),vec.end());
  for(i=vec.begin();i!=vec.end();i++){
   ans+=(i->C*now);
   now+=i->B;
   ans2+=i->C;
  }
  if(ans==0){
            printf("0 1\n");
            continue;
  }
  long long int g=gcd(ans,ans2+1);
  printf("%lld %lld\n",ans/g,(ans2+1)/g);
  vec.clear();
 }
}

pG 最大公因數問題

解法 : 輾轉相除法

#include<stdio.h>
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    while(b%a!=0)
        b%=a,a^=b,b^=a,a^=b;
    printf("%d\n",a);
}

社服美工

2013-08-27

社博歡樂題

沒有留言:

統計