暑期天天练（一）

题目链接：http://acm.hust.edu.cn/vjudge/contest/127776#overview

一。模拟

题意是给n个操作，一个初始值x，操作包括对这个x加一个数或减去一个数，输出x最终值，和不能执行减操作的次数。

注意当输入一个字符时，要用getchar把输入缓冲区里的' '吃掉。

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

int n;
LL x;
int main()
{
    cin >> n >> x;
    getchar();
    int cnt = 0,d;
    char c;
    for(int i = 0; i < n; ++i){
        cin >> c >> d;
        if(c == '+') x += d;
        else {
            if(x < d) cnt++;
            else x -= d;
        }
        getchar();
    }
    printf("%I64d %d
",x,cnt);
}

View Code

二。排序，构造

题意是给一个无序的数组，请构造出一个操作序列，把这个数组变为单调不降的，每一步操作是：对于【l,r】依次交换a[l]和a[l+1],a[l+2]和a[l+3].....

这个题目很简单其实，要把数组变有序，那么对于每一个数字，他都有一个最终的位置，只要把原来数组中的数字挪到正确的位置上就可以了，所以，问题

转化为，把一个数从i,挪到j要几步？（i <= j），显然应该把i和它右边的数互换，再和更右边的数互换，其实相当于把a[i+1]~a[j]整体左移，再把a[i]放到

j上就可以了。这里要注意从大的数字开始挪动，只要大的数确定了位置，那么小的数一定是在他左边挪动的。memmove函数很好用，比用for效率高。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e4;

int n;
int a[maxn],b[maxn];

void output(int l, int r)
{
    for(;l<r;++l){
        printf("%d %d
",l+1,l+2);
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i) {cin >> a[i];b[i] = a[i];}
    sort(b,b+n);
    for(int i = n-1; i >= 0; --i){
        int j = -1,x = b[i];
        for(j = i; j >= 0&&a[j]!=x; --j);
        if(j == -1) continue;
        output(j,i);
        memmove(a+j,a+j+1,sizeof(int)*(i-j));
        a[i] = x;
    }
}

View Code

三。DFS，回溯,数位统计

这个题看起来很烦，因为要考虑的边界条件比较多。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e4;
const int base = 7;
int n,m,mx[maxn],vis[10],len,midlen;
/*用数组表示示数的每一位，整个数组分成两半，一半是minute，一半是seconds。minute那半，长度是midlen，总共长度是len*/
/*mx数组表示能用这个数组表示的数的上限，即0-midlen-1表示的是7进制的（n-1），midlen~len表示的是7进制的（m-1）*/

void init()//把n,m转化成7进制
{
    int i = 0;
    if(n == 0)
        mx[i++] = 0;
    for(;n>0;mx[i++] = n%base,n/=base);
    midlen = i;
    reverse(mx,mx+i);
    if(m == 0)
        mx[i++] = 0;
    for(;m>0;mx[i++] = m%base,m/=base);
    len = i;
    reverse(mx+midlen,mx+i);
}
/*这个dfs就是从第0位开始，如果高位一直是mx[p]的话,显然p+1位上最大值是mx[p+1]，而如果高位是小于mx[p]，p+1位上最大值是base-1*/
/*就好比最大是360，第一位是3的话，第二位最大是6，而第一位是2的话，最高位却可以是9。。。。。特别无聊*/
/*回溯就是面临多种决策的时候，先选一种操作，更新，等计算完，把更新的东西复原，再选下一种操作，这样每种操作之间都是互不影响的*/
int dfs(int p,int flag)
{
    if(p == len)
        return 1;
    int sum = 0;
    if(flag){
        for(int x = mx[p];x>=0;--x){
            if(x == mx[p]){
                if(!vis[x]){
                    vis[x] = 1;
                    if(p+1 == midlen){
                        sum += dfs(p+1,1);
                    }
                    else 
                        sum += dfs(p+1,1);
                    vis[x] = 0;
                }
            }
            else{
                if(!vis[x]){
                    vis[x] = 1;
                    if(p+1 == midlen)
                        sum += dfs(p+1,1);
                    else
                        sum += dfs(p+1,0);
                    vis[x] = 0;
                }
            }
        }
    }
    else{
        for(int x = base-1; x >= 0; --x){
            if(!vis[x]){
                vis[x] = 1;
                if(p+1 == midlen)
                    sum+=dfs(p+1,1);
                else
                    sum += dfs(p+1,0);
                vis[x] = 0;
            }
        }
    }
    return sum;
}

int main()
{
    cin >> n >> m;
    n--,m--;
    init();
    printf("%d
",dfs(0,1));
}