Codeforces Round #663 (Div. 2)(A->C)

A：http://codeforces.com/contest/1391/problem/A

题意：

输出一个排列，满足：

对于其任意的连续子序列pi...pj都满足：pi OR pi+1 OR pi+2....OR pj>=j-i+1

解析：

顺手打了个表，发现x |  y >= max(x,y)，所以顺序输出一定是一个可行解。

#include<bits/stdc++.h>
#define N 500009
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int a[110];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;    
        for(int i=1;i<=n;i++)
            cout<<i<<" ";
            cout<<endl;
    }
}

B：http://codeforces.com/contest/1391/problem/B

题意：

n*m矩阵，除了(n,m)之外每个位置都有一个包裹，位置上仅有R,D两个可走方向。修改最少的R,D，使得每个包裹都能到达(n,m)位置。

解析：

只看最下面一行和最右边一列即可，不能超出这俩边界。

#include<bits/stdc++.h>
#define N 500009
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e2+10;
char mp[maxn][maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>mp[i][j];
        int cnt=0;
        for(int j=1;j<=m;j++)
        {
            if(mp[n][j]=='D')
                cnt++;
        }
        for(int j=1;j<=n;j++)
        {
            if(mp[j][m]=='R')
                cnt++;
        }
        cout<<cnt<<endl;
    }
}

C：http://codeforces.com/contest/1391/problem/C

解析：

很明显，直接算有环比较麻烦。那么就先看看无环怎么构造。

对于三个位置：i ,   j  ,  k 

如果 ai>aj<ak，那么就会连成环，怎么避免？单增或单减即可。

以最大的n放为例，

放第一个位置：n...........  那么n后面的要递减排列，如果递增的话，会出现环。此时为C(n-1,0)

放第二个位置：..n.........  n前面随便选一个，后面依然递减排列，为C(n-1,1)

放第三个位置：....n.......  n前面两个，必须递增排列，n后面递减排列，为C(n-1,2)

........

放最后一个位置：...........n，前面递增即可，为C(n-1,n-1)

C(n-1,0)+C(n-1,1)+.....C(n-1,n-1)==2^(n-1)

总的答案就是n!-2^(n-1)

这里需要注意一下，%的时候一律写成(x+mod)%mod，防止出现编译器给取成负数

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<map>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+7;
int l[maxn],r[maxn];
int a[maxn];
int b[8*maxn];
int vis[maxn];
ll c[maxn],d[maxn];
int pos[maxn];
const int maxn2=2e3+10;
char mp[maxn2][maxn2];
int dp[maxn2][maxn2];
int main()
{
    ll n;
    cin>>n;
    ll sum=1;
    for(int i=1;i<=n;i++)
        sum=(sum*i)%mod;
    ll md=1;
    for(int i=1;i<=(n-1);i++)
        md=(md*2)%mod;
    cout<<(sum-md+mod)%mod<<endl;
}