【noip2012 提高组 day1】

A.【NOIP2012 提高组 day1】Vigenère密码

思路：按照题目思路进行模拟

观察图后，可以发现规律

              m=c-(k-'a')；

这时若m<'a' 则 m='z'-('a'-m-1)；

然后将答案输出即可

#include<bits/stdc++.h>
using namespace std;

string k;
char m,c;
int x=0,l;

bool small(char s){
    if(s>='a'&&s<='z') return 1;
    return 0;
}

bool big(char s){
    if(s>='A'&&s<='Z') return 1;
    return 0;
}

int main(){
    cin>>k;
    l=k.size();
    getchar();
    while(scanf("%c",&c)){
        if(!small(c) && !big(c)) break;
        if(small(k[x])) m=c-(k[x]-'a');
        else if(big(k[x])) m=c-(k[x]-'A');
        if(small(c) && m<'a') m='z'-('a'-m-1);
        else if(big(c) && m<'A') m='Z'-('A'-m-1);
        x++;
        if(x>=l) x=0;
        printf("%c",m);
    }
    return 0;
}

B. 【NOIP2012 提高组 day1】国王游戏

思路：这是一道贪心题

贪心策略是将a*b的小的放在前面。

证明可使用微扰法：

先假设p1在前p2在后

所以ans1=max( a0/b1,a0*a1/b2)

然后将p1p2互换

ans2=max(a0/b2,a0*a2/b1)

我们设k1=a0/b1,k2=a0*a1/b2,k3=a0/b2,k4=a0*a2/b1

显然有 k4>k1,k2>k3

若ans1<ans2 

则 k4>k2

即：a2/b1>a1/b2

a1*b1<a2*b2

也就是只要满足这个条件，就是最优情况

这道题需要用到高精度

#include <bits/stdc++.h>
using namespace std;
int now[20010],sum[20010],ans[20010],add[20010];
struct Node {
    int a;
    int b;
    long long a_b;
}node[1010];
inline int read(){
    int x=0,f=1;
    char s=getchar();
    while(!isdigit(s)){
        f*=(s=='-')? -1:1;
        s=getchar();
    }
    do x=x*10+(s^48),s=getchar();
    while(isdigit(s));
    return x*f;
}
void times(int x) {
    memset(add,0,sizeof(add));
    for(int i=1;i<=ans[0];i++) {
        ans[i]=ans[i]*x;
        add[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    for(int i=1;i<=ans[0]+4;i++) {
        ans[i]+=add[i];
        if(ans[i]>=10) {
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
        if(ans[i]!=0) {
            ans[0]=max(ans[0],i);
        } 
    }
    return ;
}
int divite(int x) {
    memset(add,0,sizeof(add));
    int q=0;
    for(int i=ans[0];i>=1;i--) {
        q*=10;
        q+=ans[i];
        add[i]=q/x;
        if(add[0]==0 && add[i]!=0) {
            add[0]=i;
        }
        q%=x; 
    }
    return 0;
}
bool compare() {
    if(sum[0]==add[0]) {
        for(int i=add[0];i>=1;i--) {
            if(add[i]>sum[i]) return 1;
            if(add[i]<sum[i]) return 0;
        }
    }
    if(add[0]>sum[0]) return 1;
    if(add[0]<sum[0]) return 0;
}
void zh () {
    memset(sum,0,sizeof(sum));
    for(int i=add[0];i>=0;i--) {
        sum[i]=add[i];
    }
    return ;
}
bool cmp(Node a,Node b) {
    return a.a_b<b.a_b;
}
int main() {
    int n=read();
    for(int i=0;i<=n;i++) {
        node[i].a=read(),node[i].b=read();
        node[i].a_b=node[i].a*node[i].b;
    }
    sort(node+1,node+n+1,cmp);
    ans[0]=1,ans[1]=1;
    for(int i=1;i<=n;i++) {
        times(node[i-1].a);
        divite(node[i].b);
        if(compare()) {
            zh();
        }
    }
    for(int i=sum[0];i>=1;i--)
        printf("%d",sum[i]);
    return 0;
} 

C. 【NOIP2012 提高组 day1】开车旅行

设f[i][j]为在位置i走2^j轮的位置，一轮就是A走和B走一次,fa[i][j]就是A在位置i走2^j轮的距离，fb[i][j]类同。

 另外：从每个点到下一个用倍增来优化

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int maxn = 100005;
int n, x0, m, k,x1, na[maxn], nb[maxn],ans;
long long ansa = 1e5,ansb = 0ll,fa[maxn][20], fb[maxn][20], f[maxn][20];

struct node
{
    int id, high;
    bool operator < (const node & b) const {
        return high < b.high;
    }
}c[maxn];

struct node2
{
    int id, gaoducha;
    bool operator < (const node2 & b) const {
        if (gaoducha != b.gaoducha)
            return gaoducha < b.gaoducha;
        else
            return c[id].high < c[b.id].high;
    }
}temp[5];

set <node> s;

void init(int i)
{
    set <node> ::iterator it = s.find(c[i]);
    int j = 0;
    if (it != s.begin())
    {
        --it;
        temp[++j] = (node2) { it->id, abs(it->high - c[i].high) };
        if (it != s.begin())
        {
            --it;
            temp[++j] = (node2) { it->id, abs(it->high - c[i].high) };
            ++it;
        }
        ++it;
    }
    if ((++it) != s.end())
    {
        temp[++j] = (node2) { it->id, abs(it->high - c[i].high) };
        if ((++it) != s.end())
            temp[++j] = (node2) { it->id, abs(it->high - c[i].high) };
    }
    sort(temp + 1, temp + j + 1);
    nb[i] = temp[1].id;
    if (j == 1)
        return;
    na[i] = temp[2].id;
    return;
}

void query(int st, int x, long long &ta, long long &tb)
{
    for (int i = 19; i >= 0; i--)
        if (f[st][i] && fa[st][i] + fb[st][i] <= x)
        {
            ta += fa[st][i];
            tb += fb[st][i];
            x -= fa[st][i] + fb[st][i];
            st = f[st][i];
        }
    if (!na[st])
        return;
    int tempans = abs(c[na[st]].high - c[st].high);
    if (tempans <= x)
        ta += tempans;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i].high);
        c[i].id = i;
    }
    for (int i = n; i;i--)
    {
        s.insert(c[i]);
        if (i != n)
            init(i);
    }
    for (int i = 1; i <= n; i++)
    {
        int p1 = na[i], p2 = nb[na[i]];
        fa[i][0] = p1 ? abs(c[p1].high - c[i].high) : 0;
        fb[i][0] = p2 ? abs(c[p2].high - c[p1].high) : 0;
        f[i][0] = p2;
    }
    for (int j = 1; j < 20;j++) 
        for (int i = 1; i <= n; i++)
        {
            f[i][j] = f[f[i][j - 1]][j - 1];
            fa[i][j] = fa[i][j - 1] + fa[f[i][j - 1]][j - 1];
            fb[i][j] = fb[i][j - 1] + fb[f[i][j - 1]][j - 1];
        }
    scanf("%d", &x0);
    ans = 0;
    for (int i = 1; i <= n; i++)
    {
        long long ta = 0ll, tb = 0ll;
        query(i, x0, ta, tb);
        if (tb && (!ans || ansa * tb > ansb * ta))
        {
            ansa = ta;
            ansb = tb;
            ans = i;
        }
    }
    printf("%d
", ans);
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d%d", &k, &x1);
        long long ta = 0ll, tb = 0ll;
        query(k, x1, ta, tb);
        printf("%d %d
", ta, tb);
    }
    return 0;
}