学步园

UVALIve6661--Equal Sum Sets

题意：给你三个数，n，k，s，序列中每个数都不超过n且各不相同，序列共有k个数，这些数的和为s，问满足条件的序列有几个，序列无顺序。

因为数据比较小，所以我用dfs来做，但是我经常在标记部分出错，这回小白把我DFS里的循环初始改了，就过了，然后标记没起作用。。。

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100005
#define eps 1e-7
#define INF 0x7FFFFFFF
#define ff sqrt(5.0)
typedef long long ll;

int n,k,s;
int vis[155];
int ans;
void dfs(int aa,int p,int sum){
    if(p==k){
        if(sum==s){
            //cout<<aa<<" "<<p<<" "<<sum<<endl;
            ans++;
        }
        return ;
    }
    if(p>k) return ;
    if(sum>s)   return ;
    for(int i=aa;i<=n;i++){
        if(vis[i]==0){
            vis[i] = 1;
            dfs(i,p+1,sum+i);
        }
        vis[i] = 0;
    }
}
int main(){
    int i,j;
    while(scanf("%d%d%d",&n,&k,&s)!=EOF){
        if(n==0||k==0||s==0)    break;
        ans = 0;
        memset(vis,0,sizeof(vis));
        //cout<<n<<k<<s<<endl;
        for(int i=1;i<=n;i++){
            vis[i] = 1;
            dfs(i,1,i);
            //vis[i] = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}

UVALIve6662--The Last Ant【模拟】

题意：一条木棍上有一些蚂蚁，有的朝左走有的朝右走，他们如果在宽的地方相遇就能通过，在窄的地方相遇就掉头往回，速度恒定，问多久所有蚂蚁都能爬出去和最后一只出去的蚂蚁序号。

模拟每一秒，我写了两遍，第一次写矬了，改来改去越搞代码越多越不知道bug在哪，索性重写了一遍。每秒钟让蚂蚁走一格，都走完之后按位置排序，然后判断如果两个蚂蚁在同一位置就让它们掉头，直到结束。

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100005
#define eps 1e-7
#define INF 0x7FFFFFFF
#define ff sqrt(5.0)
typedef long long ll;

struct node{
    int num,pos;
    char dir;
}a[25];
bool cmp(node x,node y){
    return x.pos<y.pos;
}
int main(){
    int l,n,i;
    int cnt,ans;
    while(scanf("%d%d",&n,&l)!=EOF){
        if(n==0&&l==0)  break;
        cnt = ans = 0;
        for(i=0;i<n;i++){
            getchar();
            cin>>a[i].dir>>a[i].pos;
            a[i].num = i+1;
        }
        sort(a,a+n,cmp);
        node ant[2];
        int flag;
        while(1){
            cnt++;
            flag = 0;
            for(i=0;i<n;i++){
                if(a[i].pos<=0||a[i].pos>=l)    continue;
                if(a[i].dir=='R')   a[i].pos++;
                else    a[i].pos--;
                if(a[i].pos==0||a[i].pos==l){
                    ant[flag] = a[i];
                    flag++;
                }
            }
            sort(a,a+n,cmp);
            for(i=0;i<n-1;i++){
                if(a[i].pos==a[i+1].pos){
                    if(a[i].dir=='L')   a[i].dir = 'R';
                    else    a[i].dir = 'L';
                    if(a[i+1].dir=='L')   a[i+1].dir = 'R';
                    else    a[i+1].dir = 'L';
                }
            }
            int ccc = 0;
            for(i=0;i<n;i++){
                if(a[i].pos<=0||a[i].pos>=l)    ccc++;
            }
            if(ccc==n)  break;
        }
        if(flag==1) ans = ant[0].num;
        else{
            if(ant[0].dir=='L') ans = ant[0].num;
            else    ans = ant[1].num;
        }
        cout<<cnt<<" "<<ans<<endl;
    }
    return 0;
}

UVALIve6663--Count the Regions【离散化+搜索】

传送门

UVALIve6664--Clock
Hands【模拟】

传送门