2017 ACM Jordanian Collegiate Programming Contest

A Chrome Tabs

题目链接
题意：1~n的开关，可以选择对于一个开关右边所有开关翻转，或者左边所有开关翻转。初始全为关，要求除第k个开关关着，其余全开的最小步数
思路：边界为1，中间为2，长度1特判

    #include<cstdio>

    int T,n,k;
    int main(){
        freopen("tabs.in","r",stdin);
        scanf("%d",&T);
        while(T--){
            scanf("%d%d",&n,&k);
            if(n==1)puts("0");
            else if(k==1||k==n)puts("1");
            else puts("2");
        }
    }

B OverCode

题目链接
思路：排序后贪心

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 5;
    int a[maxn];

    int main() {
        freopen("overcode.in","r",stdin);
        int T;
        scanf("%d", &T);
        while (T--) {
            int n;
            scanf("%d", &n);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
            }
            sort(a + 1, a + 1 + n);
            int cnt = 0;
            for (int i = 1; i <= n;) {
                int j = i + 5;
                if (j > n)break;
                if (a[j] - a[i] > 1000) {
                    i++;
                }
                else {
                    cnt++;
                    i += 6;
                }
            }
            printf("%d\n", cnt);
        }
    }

C A message for you!

题目链接
题意：ABC..13个字符，每个字符付一个权值，求除给定字符串中字符之外剩余最大权值的字母
思路：排序，贪心

    #include <bits/stdc++.h>

    using namespace std;

    char s[20];
    int book[20];

    struct node{
        int f;
        int id;
    }nod[20];

    bool cmp(node a,node b){
        return a.f>b.f;
    }

    int main(){
        freopen("scoreboard.in","r",stdin);
        int t;
        scanf("%d",&t);
        while(t--){
            int k;
            memset(book,0,sizeof book);
            scanf("%d",&k);
            scanf("%s",s);
            for(int i=0;i<k;i++)
                book[s[i]-'A'+1]=1;
            for(int i=1;i<=13;i++){
                scanf("%d",&nod[i].f);
                nod[i].id=i;
            }

            sort(nod+1,nod+14,cmp);

            for(int i=1;i<=13;i++){
                if(book[nod[i].id])
                    continue;
                printf("%c\n",nod[i].id+'A'-1);
                break;
            }
        }
    }

D Test Cases

题目链接
题意：寻找存在多少个点对，满足对于区间 [l,r]，其出现次数为奇数的值仅为一个。
思路：n^2暴力，以前缀记录奇数个数，开1e6的桶记录状态

    #include <bits/stdc++.h>

    #define maxn 5005
    using namespace std;

    int n;
    int a[maxn];
    int vis[1000005];

    void input(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
    }

    void solve(){
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++)
                vis[a[j]]=0;

            int odd=0;
            for(int j=i;j<=n;j++){
                vis[a[j]]?odd--:odd++;
                vis[a[j]]^=1;
                if(odd==1)
                    ans++;
            }
        }
        printf("%d\n",ans);
    }

    int main(){
        freopen("cases.in","r",stdin);
        int t;
        scanf("%d",&t);
        while(t--){
            input();
            solve();
        }
    }

E Robot I - Instruction Reduction

题目链接
题意：给出n*m的图，起始机器人位置、朝向以及机器人的行动步骤，R代表机器人顺时针转向，F val代表向当前方向走val步，当走到头就向右转继续走。
思路：记录每个方向最后走的真正方向，按照步骤模拟，压缩走的步数。

    #include <bits/stdc++.h>

    #define maxn 505
    using namespace std;

    int r,c,q;
    int sr,sc;
    char sdir;
    int dir;

    int tx[4]={0,1,0,-1};
    int ty[4]={-1,0,1,0};
    char g[maxn][maxn];
    int f[maxn][maxn][5];
    int a[(maxn<<1)*(maxn<<1)];
    pair <int,int> pir[maxn<<1];

    void input(){
        scanf("%d%d%d",&r,&c,&q);
        scanf("%d%d %c",&sr,&sc,&sdir);
        if(sdir=='U') dir=0;
        else if(sdir=='R') dir=1;
        else if(sdir=='D') dir=2;
        else dir=3;

        for(int i=1;i<=r;i++){
            scanf("%s",g[i]+1);
        }

        for(int i=2;i<r;i++){
            for(int j=2;j<c;j++){
                if(g[i][j]=='.'){
                    for(int d1=0;d1<4;d1++){
                        for(int d2=0;d2<4;d2++){
                            int dd=(d1+d2)%4;
                            if(g[i+ty[dd]][j+tx[dd]]=='.'){
                                f[i][j][d1]=dd;
                                break;
                            }
                        }
                    }
                }
            }
        }

        int sty=sr;int stx=sc;int stdir=dir;
        int cnt=0;
        for(int i=1;i<=q;i++){
            char flag;
            int step;
            scanf(" %c",&flag);
            if(flag=='R'){
                dir=(dir+1)%4;
            }else{
                scanf("%d",&step);
                while(step--){
                    dir=f[sr][sc][dir];
                    sr+=ty[dir];
                    sc+=tx[dir];
                    a[++cnt]=dir;
                }
            }
        }

        sr=sty;sc=stx;dir=stdir;

        int ans=0;
        for(int i=1;i<=cnt;i++){
            for(int k=0;k<4;k++){
                if(f[sr][sc][dir]==a[i]){
                    dir=a[i];
                    sr+=ty[dir];
                    sc+=tx[dir];

                    if(ans&&pir[ans].first==1){
                        ++pir[ans].second;
                    }else
                        pir[++ans]={1,1};
                    break;
                }else{
                    pir[++ans]={2,0};
                    dir=(dir+1)%4;
                }
            }
        }
        printf("%d\n",ans);
    }

    int main(){
        freopen("reduce.in","r",stdin);
        int t;
        scanf("%d",&t);
        while(t--){
            input();
    //        solve();
        }
    }

G WiFi Password

题目链接
题意：对于给定的数组，求最长子序列满足或运算结果小于k
思路：位运算，递推

    #include<iostream> 
    #include<cstdio>
    #include<cstring>
    #include<map>
    #include<vector> 
    #include<set>
    #include<queue>
    #include<algorithm>
    #include<string>
    #include<cmath>
    #include<stack>
    #include<functional>
    #include<bitset>
    #define ll long long
    #define maxn 100002
    const int mod = 1e9 + 7;

    using namespace std;
    int num[maxn];
    int value[22];
    int t, n, v;
    bool check(){
        int i, sum = 0;
        for(i = 0;i <= 18;i++){
            if(value[i]){
                sum += (1 << i);
            }
        }
        return sum <= v;
    }
    int main(void){
        freopen("wifi.in","r",stdin);
        int i, j, l, ans;
        scanf("%d",&t);
        while(t--){
            ans = 0;
            for(i = 0;i <= 18;i++){
                value[i] = 0;
            }
            scanf("%d %d",&n,&v);
            for(i = 0;i < n;i++){
                scanf("%d",&num[i]);
            }
            l = 0;
            for(i = 0;i < n;i++){
                for(j = 0;j <= 18;j++){
                    if(num[i] & (1 << j)){
                        value[j]++;
                    }
                }
                while(!check()&&l <= i){
                    for(j = 0;j <= 18;j++){
                        if(num[l] & (1 << j)){
                            value[j]--;
                        }
                    }
                    l++;
                }
                ans = max(ans,i - l + 1);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

M Winning Cells

题目链接
题意：一个n*n的格子，每个格子存在先后手，可以选择向上或向左走1~k任意步，求先手到(1,1)格的可行解格数
思路：找规律

    #include<iostream>  
    #include<cstdio>
    #include<cstring>
    #include<map>
    #include<vector> 
    #include<set>
    #include<queue>
    #include<algorithm>
    #include<string>
    #include<cmath>
    #include<stack>
    #include<functional>
    #include<bitset>
    #define ll long long
    #define maxn 100002
    const int mod = 1e9 + 7;

    using namespace std;
    int main(void){
        freopen("chess.in","r",stdin);
        int t;
        ll n, k, ans;
        scanf("%d",&t);
        while(t--){
            scanf("%I64d %I64d",&n,&k);
            if(n < (k + 1)){
                ans = n * n - n;
            }
            else{
                ans = n * n - (n / (k + 1)) * (n / (k + 1)) * (k + 1) - 2 * (n / (k + 1) * (n % (k + 1))) - n %(k + 1);
            }
            printf("%I64d\n",ans);
        }
        return 0;
    }