Chengrui's Blog

2014海大ACM总结

发表于 2014-12-28 分类于 Summaries and pictures Disqus：

又一次出校比赛，感觉答题时比之前那次好多了。但是成绩并不理想。

三道Ac的是A、B、H。一开始A题，用了cin和cout居然TLE一次，以后得注意了。B题，一开始貌似有点问题，一直超时，在优化的时候几乎想了所有的优化方式连++i的时间比i++时间短都用上了，后来题目更正很容易Ac了。H题，锟神打的代码，WA，我debug之后过了。

再说说主要由我写的代码D、E、G题，写了三道题，写废了三道题。

D题迷宫的，一开始天真的以为是道DFS回溯题，很高兴地打了代码。。交之后TLE，又加了个剪枝条件，依旧TLE。。后来脑补了一个情况发现，DFS稳稳超时，无解。。这就浪费了三四十分钟。

E题求三角形角平分线交点的题，木有模板，手算了一半，发现不好算就放弃了。。

G题一开始用set存空白内存起点、终点、长度。两种操作写好了一种，第二种卡住了。然后锟神开始敲C题，我继续想G题。差六七分钟结束时，知道之前哪里错了，应该写个函数处理，但是发现打不完了。。

再说说很坑的现场改题。韩祎看了5个小时的C题，直到结束了我们都不知道C题改题了。。还有A题改了精度，B题改了格式，E题改了输入输出和格式。。比青岛理工那次还坑。。

虽然比的不好，但是收获还是有的。

以后能不用流输入和流输出就不用，真是太慢的。

比赛现场的通知一定要听清，说不准就一直坑在这上面了。

写题之前先看清楚了，别写完了才脑补出来方法根本就是错的。

有的题，单独列出函数处理会简单很多。

模板特别重要，旁边那组有模板，轻松过E题。。

下一步的计划，还是先学好线代高数，尽量学好图论数论动规。。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

ACM班级对抗赛总结

发表于 2014-12-20 分类于 Summaries and pictures Disqus：

总算比完了，写写比赛的收获。

预赛时长2.5h，我参加的第二场，上午我们班是第六，感觉进决赛没什么压力，打得比较轻松，47min Ac了三道题之后，剩下一个多小时一道题没出。。有道题加上卡oj的bug交C++，故意交错的CE，一共错了十次。。回宿舍换了Xcode之后马上知道是哪错了。。Xcode太好用了，以至于有些依赖它进行debug。。

决赛时长4h，开场35min，Ac了三道题，然后一个多小时什么都没出。。期间试了除了一道数学几何题之外所有的题。。后来看有人Ac了那道之后才去做的。。过了好久，又Ac了一道格式坑的题。。表面上比得还可以，如果能直接提交C++还可以少CE4次，就是第一了。但是这次比赛却隐藏着很大的的问题。。做水题很快，稍微有点坑的题，就卡住很久。碰到几何题，公式推导题直接跳过，都不敢做。。只会做一些比较常规类型的题目，这次E、F、G三道题难一些，一般做法都会超时，需要优化算法，可我一个都没做出来。。

代码能力不是轻松就能提高的，还是得多加练习。只刷水题是不会有很大提高的。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa 11809 - Floating-Point Numbers（取对数）

发表于 2014-12-18 分类于 AOAPC II ， Chapter 03. Arrays and Strings Disqus：

输入一个用AeB表示的浮点数，求他的尾码和阶码的大小。

一开始准备用double保存所有情况，后来发现最大值是2⁽²30)会溢出，直接算不可行，最后使用去对数解决。

首先进行打表，求出尾码从0到9时表示浮点数的标准值。

对于读入的AeB，用streamstring读出A、B的值，然后用对数法求对应的m和e，当所求值与之前算的标准值误差小于EPS时就是所求解。

#include<iostream>
#include<string>
#include<sstream>
#include<cmath>
const double EPS=1e-13;
using namespace std;
long double stdm[12],a=0.0;
int b=0;
bool read(){
    string s;
    if(!(cin>>s)||s=="0e0") return false;
    s[17]=' ';
    stringstream ss(s);
    ss>>a>>b;
    return true;
}
void solve(){
    long double k,l;
    int m=0,e=0;
    for(int i=0;i<12;i++){
        k=a/stdm[i];
        l=log2((log10(k)+b)*log2(10.0)+1);
        e=(int)floor(l+0.5);
        if(fabs(e-l)<EPS){
            m=i;
            break;
        }
    }
    cout<<m<<" "<<e<<endl;
    return;
}
int main(){
    for(int i=0;i<12;i++)
        stdm[i]=1-pow(0.5,i+1);
    while(read()){
        solve();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa做题阶段性总结（2014-12-08）——百题完结

发表于 2014-12-08 分类于 Summaries and pictures Disqus：

昨天刷完了集训队的百题，一共刷了56天，目测是14级第一个进队的。（最后这几天，刷水题丧心病狂，找水题的时间比做题还长。。）

写写以后的打算，现在到期末是不准备再刷题了，专心搞搞线代高数什么的。

假期准备好好看看紫书，最好看完前11章，留最后一章高级专题慢慢理解。（目测看不了那么多。。）还有就是感觉该学些操作系统底层的知识了，以后肯定会有用。

有些事还是不写了吧，还是接着努力了。。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa百题留念

发表于 2014-12-07 分类于 Summaries and pictures Disqus：

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa 11646 - Athletics Track（几何）

发表于 2014-12-07 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

给出跑道内矩形的长宽比，求长和宽，跑道一圈400米，两边的弧属于同一个圆。

简单的几何题，求出长和宽的表达式输出就好。

#include<cstdio>
#include<cmath>
const double pi=acos(-1);
int main(){
    int t=0;
    double a,b;
    while(scanf("%lf : %lf",&a,&b)!=EOF){
        a/=b,b=1;
        double r,x,h;
        r=sqrt(a*a+1);
        h=r*atan(b/a);
        x=200/(a+h);
        printf("Case %d: %.10lf %.10lf\n",++t,a*x,b*x);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa 11136 - Hoax or what（可重集）

发表于 2014-12-07 分类于 AOAPC Training Guide ， Chapter 3. Data Structures ， Fundamental Data Structures Disqus：

超市促销活动，每天从箱子里把最大和最小的小票拿出来，送出等于其差值的奖金，求送出的总和。

使用可重集本身就是有序排列，不会超时每次从中取出头尾两个元素求差的和。

要注意数据量大，用cin、cout要关闭流同步，还有求和应该使用long long。

#include<iostream>
#include<set>
using namespace std;
multiset<int> a;
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n){
        long long sum=0;
        a.clear();
        while(n--){
            int m,k;
            cin>>m;
            while(m--){
                cin>>k;
                a.insert(k);
            }
            multiset<int>::iterator it1=a.begin(),it2=--a.end();
            sum+=*it2-*it1;
            a.erase(it1);
            a.erase(it2);
        }
        cout<<sum<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa 11609 - Teams（组合数＋快速幂）

发表于 2014-12-07 分类于 AOAPC Training Guide ， Chapter 2. Mathematics ， Basic Problems Disqus：

有n个人，选一个或多个人参赛，其中一人为队长，求有多少种选法，结果对100000007取模。

根据题意结果为1C(n,1)+2C(n,2)+……＋n*C(n,n)对100000007取模的值。

有组合数公式：1C(n,1)+2C(n,2)+……＋nC(n,n)=n2^(n-1)

然后用快速幂取模就好了。

#include<iostream>
using namespace std;
const long long maxn=1000000007;
long long modexp(int a,int b){
    long long ret=1;
    long long tmp=a;
    while(b){
        if(b&1) ret=ret*tmp%maxn;
        tmp=tmp*tmp%maxn;
        b>>=1;
    }
    return ret;
}
int main(){
    int n,t=0;
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        cout<<"Case #"<<++t<<": ";
        cout<<(modexp(2,a-1)*a)%maxn<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa 11889 - Benefit

发表于 2014-12-07 分类于 AOAPC Training Guide ， Chapter 2. Mathematics ， Basic Problems Disqus：

b一定为c/a的倍数，lcm=ab/gcd,lcmgcd=a*b。然后枚举。

PS：一开始忽略了相乘会爆掉int这个问题。。WA了两次。。

#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a,int b) {
    return (b?gcd(b,a%b):a);
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,c;
        cin>>a>>c;
        if(c%a){
            cout<<"NO SOLUTION"<<endl;
            continue;
        }
        int t=c/a;
        for(int b=t;b<=c;b+=t){
            long long i=(long long)c*gcd(a,b),j=(long long)a*b;
            if(i==j){
                cout<<b<<endl;
                break;
            }
        }
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

UVa 11388 - GCD LCM

发表于 2014-12-06 分类于 AOAPC Training Guide ， Chapter 2. Mathematics ， Basic Problems Disqus：

求以给出两数为最大公倍数和最小公约数的两个数，且第一个数要求最小。简单分析就出来了。

#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    while(n--){
        int g,l;
        cin>>g>>l;
        if(l%g) cout<<"-1"<<endl;
        else cout<<g<<" "<<l<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **