Educational Codeforces Round 44 (Rated for Div. 2)

A. Chess Placing

思路：一半奇数位，一半偶数位。一一对应即可，注意别忘记排序

B. Switches and Lamps

思路：暴力模拟O(n*m)

C. Liebig's Barrels【贪心】

思路：sort后，求出最右边的木板最大的区间范围[1,r]。尽量让h小的放在一起，假设r个里面能造t个木桶。那么有不等式 r-k*t<=n-t ，求出最大的t。然后[kt+1,r]不能再构成桶了，于是取kt+1，从r往前取n-t-1个板。

D. Sand Fortress【贪心+二分】

思路:手动模拟。发现堆数x越大，能堆的城堡范围在[k,max]越大。只要n在[1,max]的范围内，则必定存在一个x'<=x使得其满足n堆的沙丘.

#pragma comment(linker, "/stack:100000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
#define setp cout << fixed << setprecision(15)
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+5;
typedef long long ll;
ll n,h;
ll cul(ll x){
    return x*(x+1)/2;
}
bool check(ll k){
    if(k<=h){
        if( (1+k)*k/2 >= n) return true;
        else    return false;
    }
    ll sum=0;
    if(h%2==0){
        ll best=k-h;
        ll most=h+best/2;
        if(k%2==1)  sum=2*cul(most)-cul(h-1);
        else    sum=cul(most)+cul(most-1)-cul(h-1);
    }
    else{
        ll best=k-h;
        ll most=h+best/2;
        if(k%2==0)  sum=2*cul(most)-cul(h-1);
        else    sum=cul(most)+cul(most-1)-cul(h-1);
    }
//    cout <<"sum="<<sum<<endl;
//    cout << sum-n << endl;
    if(sum>=n)  return true;
    else return false;
}

int main(void){
    fst;
    cin >> n >> h;
    ll l=1,r=2e9,ans;
//    cout <<check(7) << endl;;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid))  /*cout <<"~"<<mid<<endl,*/ans=mid,r=mid-1;
        else    l=mid+1;
    }
    cout << ans << endl;

    return 0;
}

E. Pencils and Boxes(DP)

思路:把当前区间划分成若干个区间

条件1:每个区间max-min<=d

条件2:区间大小不小于k个

dp[i]:前i个物品是否能按要求划分,能是1,否则为0;

根据条件1,可以判断下届L,根据>=k可以判断出上届R.那么只要当dp[L~R]有一个成立,那么dp[i]就一定可以成立,用树状数组logn维护.这题问区间是否能划分,重点考虑DP

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
#define setp cout << fixed << setprecision(15)
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=5e5+5;
typedef long long ll;
ll a[N];
int t[N];
ll n,k,d;
void update(ll x){
    for(ll i=x;i<=n;i+=i&(-i))  t[i]+=1;
}

ll query(ll x){
    ll ans=0;
    for(ll i=x;i;i-=i&(-i)) ans+=t[i];
    return ans;
}

int main(void){
    fst;
    cin >>n >> k>>d;
    for(ll i=1;i<=n;i++)   cin >> a[i];
    sort(a+1,a+1+n);
    for(ll i=k;i<=n;i++){
        ll l=lower_bound(a+1,a+1+n,a[i]-d)-a;
        l--;
        if(l==0)    l=1;
        ll r=i-k;
        if(a[i]-a[1]<=d){
            update(i);
            continue;
        }
        if(r<l) continue;
        ll sum=query(r)-query(l-1);
        if(sum>0)   update(i);
    }
    if(query(n)-query(n-1)>0)    cout <<"YES"<<endl;
    else    cout <<"NO"<<endl;

    return 0;
}

F. Isomorphic Strings(哈希)

思路:两个串s1,s2的每一个位置存在一一映射的关系.那么把s1串的字母'A'出现的位置用一个数字来代表,'B'同理. 对于串s2,也同理. 那么sort看看是不是2个串所有字母的代表数字相同

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
#define setp cout << fixed << setprecision(15)
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+5;
typedef long long ll;
char s[N];
int n,q;

struct Hash{
    ll Seed,Mod;
    ll sum[26][N],bas[N];
    void init(){
        bas[0]=1;
        for(int i=1;i<=n;i++)  bas[i]=bas[i-1]*Seed%Mod;

        for(int i=0;i<26;i++){
            for(int j=1;j<=n;j++){
                sum[i][j]=( sum[i][j-1]*Seed%Mod+ (s[j]-'a'==i?1:0) )%Mod;
            }
        }
    }
    ll gethash(ll *t,int l,int r){
        return (((t[r]-t[l-1]*bas[r-l+1]%Mod)+Mod)%Mod);
    }
}gen[2];

void solve(){
    int x,y,len;
    scanf("%d%d%d",&x,&y,&len);
    ll a[2][30],b[2][30];
    for(int i=0;i<=1;i++){
        for(int j=0;j<26;j++){
            a[i][j]=gen[i].gethash(gen[i].sum[j],x,x+len-1);
            b[i][j]=gen[i].gethash(gen[i].sum[j],y,y+len-1);
        }
    }
    for(int i=0;i<=1;i++)
        sort(a[i],a[i]+26),sort(b[i],b[i]+26);
//    for(int i=0;i<26;i++){
////        printf("%d -> %I64d %I64d\n",i,a[1][i],b[1][i]);
//    }
//    for(int i=0;i<=1;i++){
        for(int j=0;j<26;j++){
            if(a[0][j]!=b[0][j] || a[1][j]!=b[1][j]){
                printf("NO\n");
                return ;
            }
        }
//    }
    printf("YES\n");
    return ;
}

void hash_init(){
    gen[0].Seed=146527,gen[0].Mod=1e9+9;
    gen[1].Seed=19260817,gen[1].Mod=998244353;
    for(int i=0;i<=1;i++){
        gen[i].init();
    }
}

int main(void){
//    fst;
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    hash_init();
    while(q--){
        solve();
    }

    return 0;
}