nenu contest

http://vjudge.net/vjudge/contest/view.action?cid=54393#overview

A n^2能过 对第二个n我二分了一下，快了一点点，nlogn

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 double judge[];

 int main(){

     for(int i=;i<;i++){

         judge[i]=i*;

     }

     double now;

     int n,s;

     while(~scanf("%d%d",&n,&s)){

         int sum=;

         for(int i=;i<n;i++){

             scanf("%lf",&now);

             int L=lower_bound(judge,judge+,now)-judge;

             if(judge[L]>now) L--;

             if(judge[L]<=now&&now<=judge[L]+) sum++;

         }

         printf("%.1f\n",sum*(+0.2*s));

     }

     return ;

 }

A LEE的on的方法也很值得借鉴，竟然比我二分的慢，不知为何，数据小吧

 #include<cstdio>

 const double eps = 1e-;

 int main() {

     int n, s, cnt;

     double t;

     while (~scanf("%d%d", &n, &s)) {

         cnt = ;

         while (n--) {

             scanf("%lf", &t);

             int T = int(t);

             if (T %  <  || (T %  ==  && (t-T) < eps)) {

                 cnt++;

             }

         }

         printf("%.1f\n", cnt*( + 0.2*s));

     }

     return ;

 }

B %X scanf printf 16进制输入输出

 #include<cstdio>

 #include<cstring>

 const int M=;

 char op[M];

 int main(){

     int t,sa,sb;

     while(~scanf("%d",&t)){

         while(t--){

             scanf("%X%X",&sa,&sb);

             getchar();

             gets(op);

             int lp=strlen(op);

             for(int i=;i<lp;i++){

                 if(op[i]==''){

                     if(op[i+]=='A'){

                         sa+=sb;

                     }

                     else{

                         sb+=sa;

                     }

                     i+=;

                 }

                 else if(op[i]=='F'){

                     if(op[i+]=='A'){

                         sa+=sa;

                     }

                     else{

                         sb+=sb;

                     }

                     i+=;

                 }

             }

             printf("%X %X\n",sa,sb);

         }

     }

     return ;

 }

C 比赛时n^2logn 900ms压线过，事实上nlogn就行了

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<map>

 #define mt(a,b) memset(a,b,sizeof(a))

 using namespace std;

 const int M=;

 class UnionFindSet {  //并查集

     int par[M];

 public:

     void init() {

         mt(par,-);

     }

     int getroot(int x) {

         int i=x,j=x,temp;

         while(par[i]>=) i=par[i];

         while(j!=i) {

             temp=par[j];

             par[j]=i;

             j=temp;

         }

         return i;

     }

     bool unite(int x,int y) {

         int p=getroot(x);

         int q=getroot(y);

         if(p==q)return false;

         if(par[p]>par[q]) {

             par[q]+=par[p];

             par[p]=q;

         } else {

             par[p]+=par[q];

             par[q]=p;

         }

         return true;

     }

 }gx;

 map<string,int> mp;

 string str;

 int main(){

     int n,m;

     char op[];

     while(~scanf("%d",&n)){

         bool flag=false;

         gx.init();

         mp.clear();

         for(int i=;i<=n;i++){

             scanf("%d",&m);

             while(m--){

                 flag=true;

                 scanf("%s",op);

                 str=(string)op;

                 if(!mp[str]){

                     mp[str]=i;

                 }

                 else{

                     gx.unite(mp[str],i);

                 }

             }

         }

         if(!flag){

             printf("%d\n",n);

             continue;

         }

         int ans=;

         for(int i=;i<=n;i++){

             if(i==gx.getroot(i)) ans++;

         }

         printf("%d\n",ans-);

     }

     return ;

 }

I n^2能过400ms on单调队列62ms

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 const int M=;

 int a[M],b[M];

 int main(){

     int n,m;

     while(~scanf("%d%d",&n,&m)){

         for(int i=;i<n;i++){

             scanf("%d",&a[i]);

         }

         for(int i=;i<m;i++){

             scanf("%d",&b[i]);

         }

         int la=,lb=,ans=1e9;

         while(la!=n&&lb!=m){

             ans=min(ans,abs(a[la]-b[lb]));

             if(a[la]>b[lb]) lb++;

             else la++;

         }

         printf("%d\n",ans);

     }

     return ;

 }

J  on 水题

 #include<cstdio>

 typedef __int64 LL;

 const int M=;

 char a[M][];

 int main(){

     int n;

     while(~scanf("%d",&n)){

         for(int i=;i<n;i++){

             scanf("%s",a[i]);

         }

         LL ans=;

         LL sum=;

         for(int i=n-;i>=;i--){

             if(a[i][]=='W') ans+=sum;

             else sum++;

         }

         printf("%I64d\n",ans);

     }

     return ;

 }