Educational Codeforces Round 16 C 思维 D 中国剩余(不互质) E dp递推,思维

题意：数字1到n*n，排成n行n列，要使得每行、每列和两条主对角线上的数之和为奇数。

tags：从中心开始观察，每一圈都可以是奇偶交替，所以搞几个for循环就好。　　注：多动手在草稿纸上画。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define F(i,b,a)  for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 2e5+10;

int a[500][500], n;
int main()
{
    scanf("%d", &n);
    int m=n/2+1, t=1;
    FF(i,1,m) {
        F(l,m,i) a[i][l]=t++;
        FF(l,i+1,n-i+1) a[l][i]=t++;
        FF(l,i+1,n-i+1) a[n-i+1][l]=t++;
        F(l,n-i,i) a[l][n-i+1]=t++;
        F(l,n-i,m+1) a[i][l]=t++;
    }
    FF(i,1,n) {
        FF(j,1,n) printf("%d  ", a[i][j]);
        puts("");
    }

    return 0;
}

View Code

D. Two Arithmetic Progressions

题意：有y=a1*x1+b1，y=a1*x2+b2。给出a1、b1、a2、b2、L、R，求在[L,R]内，有多少个满足条件的y。

tags：终于体会到有板子的好处了。

很明显，拓展中国剩余定理。有个点，y可以先限制范围，即L=max(L, max(a[1], a[2])) 。然后合并以后，不知道怎么确定出的范围，23333。。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 10;

ll L, R, cur, mm;
ll a[N], m[N];  
    
ll gcd(ll a,ll b)  
{  
    return b? gcd(b, a % b) : a;  
}  
void extend_Euclid(ll a, ll b, ll &x, ll &y)  
{  
    if(b == 0)  
    {  
        x = 1;  
        y = 0;  
        return;  
    }  
    extend_Euclid(b, a % b, x, y);  
    ll tmp = x;  
    x = y;  
    y = tmp - (a / b) * y;  
}  
ll Inv(ll a, ll b)  
{  
    ll d = gcd(a, b);  
    if(d != 1) return -1;  
    ll x, y;  
    extend_Euclid(a, b, x, y);  
    return (x % b + b) % b;  
}  
bool merge(ll a1, ll m1, ll a2, ll m2, ll &a3, ll &m3)  
{  
    ll d = gcd(m1, m2);  
    ll c = a2 - a1;  
    if(c % d) return false;  
    c = (c % m2 + m2) % m2;  
    m1 /= d;  
    m2 /= d;  
    c /= d;  
    c *= Inv(m1, m2);  
    c %= m2;  
    c *= m1 * d;  
    c += a1;  
    m3 = m1 * m2 * d;  
    a3 = (c % m3 + m3) % m3;  
    return true;  
}  
ll CRT(ll a[], ll m[], int n)  
{  
    ll a1 = a[1];  
    ll m1 = m[1];  
    for(int i=2; i<=n; i++)  
    {  
        ll a2 = a[i];  
        ll m2 = m[i];  
        ll m3, a3;  
        if(!merge(a1, m1, a2, m2, a3, m3))  
            return -1;  
        a1 = a3;  
        m1 = m3;  
    }  
    cur=a1, mm=m1;
    return (a1 % m1 + m1) % m1;  
}  

int main()
{
    scanf("%lld %lld %lld %lld %lld %lld", &m[1], &a[1], &m[2], &a[2], &L, &R);
    L=max(L, max(a[1], a[2]));
    ll ans=CRT(a, m, 2);
    if(ans==-1)    return 0*printf("0
");
    ans=0;
    if(cur >= L)  cur-= ((cur-L)/mm+1)*mm; 
    if(L <= R)  ans = (R-cur)/mm-(L-1-cur)/mm; 
    printf("%lld
", ans);

    return 0;
}

View Code

E. Generate a String

题意：要得到n个字符，有三种操作：输入一个花费x；删除一个花费x；复制粘贴花费y。

tags：很容易想到dp，增加和复制操作好办，但删除很麻烦。由复制可以联想到奇偶性。当要得到偶数个字符时，通过删除得到肯定是不如增加和复制得到快。想到这里就明白直接递推就行。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define F(i,b,a)  for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 1e7+10;

int n, x, y;
ll dp[N];
int main()
{
    scanf("%d%d%d", &n, &x, &y);
    FF(i,1,n) {
        if(i&1) dp[i]=min(dp[i-1]+x, dp[(i+1)/2]+y+x);
        else dp[i]=min(dp[i-1]+x, dp[i/2]+y);
    }
    printf("%lld
", dp[n]);

    return 0;
}

View Code