Codeforces Round #806 (Div. 4)D~G

Problem - G - Codeforces

动态规划。设f[i][j]为第i位使用j次免费后的最大值。

#include 
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define debug(a) cout<<#a<<"="<ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const int maxn=1e5+6;

int n,m;
int a[maxn];
ll f[maxn][31];
int main(){
    int t=rr();
    while (t--) {
        n=rr(),m=rr();
        for(int i=1;i<=n;i++) {
            a[i]=rr();
        }
        for(int i=0;i<=n;i++) {
            for(int j=0;j<31;j++)
                f[i][j]=-inf;
        }
        f[1][0]=a[1]-m,f[1][1]=a[1]>>1;
        for(int i=2;i<=n;i++) {
            f[i][0]=f[i-1][0]+a[i]-m;
            for(int j=1;j<31;j++) {
                // 前一次使用到j-1次免费，那么当前必须免费
                // 前一次已经使用j次免费，那么当前一定不免费
                f[i][j]=max(f[i-1][j-1]+(j==30?a[i]>>j),
                            f[i-1][j]+(j==30?0:((a[i]>>j)-m)));
            }
        }
        ll ans=f[n][0];
        for(int i=1;i<31;i++) {
            ans=ans 
错误思路 
最后输出有负数。因为他妈逼的j==30没有特判。研究了一下午。
 
#include 
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define debug(a) cout<<#a<<"="<ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const int maxn=1e5+6;

int n,m;
int a[maxn];
ll f[maxn][31];
int main(){
    int t=rr();
    while (t--) {
        n=rr(),m=rr();
        for(int i=1;i<=n;i++) {
            a[i]=rr();
        }
        for(int i=0;i<=n;i++) {
            for(int j=0;j<31;j++)
                f[i][j]=-inf;
        }
        f[1][0]=a[1]-m,f[1][1]=a[1]>>1;
        for(int i=2;i<=n;i++) {
            f[i][0]=f[i-1][0]+a[i]-m;
            for(int j=1;j<31;j++) {
                int now=a[i]>>j;
                // 前一次使用到j-1次免费，那么当前必须免费
                // 前一次已经使用j次免费，那么当前一定不免费
                f[i][j]=max(f[i-1][j-1]+now,f[i-1][j]+now-m);
            }
        }
        ll ans=f[n][0];
        for(int i=1;i<31;i++) {
            ans=ans 
F. Yet Another Problem About Pairs Satisfying an Inequality 
Problem - F - Codeforces
 
O(n)思路 
O(n)复杂度的办法。pre[i]保存到i为止多少个a[i]满足a[i] 
#include 

using namespace std;
int t, n, a[200005], pref[200005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        long long ans=0;
        for (int i=1; i<=n; i++) {
            cin >> a[i];
            pref[i]=pref[i-1]+(a[i]
                ans+=pref[max(0, a[i]-1)];
            }
        }
        cout << ans << "n";
    }
    return 0;
}
 
O(nlog)思路 
类似单调队列。lower_bound查询第一个大于等于a[i]的下标，下标-1就是小于的结果，求累加和即可。只比上面慢了十几毫秒。
 
#include 
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define debug(a) cout<<#a<<"="<ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const int maxn=2e5+6;

int n,m;
ll a[maxn];
void init() {
    n=rr();
    for(int i=1;i<=n;i++) {
        a[i]=rr();
    }
}
int main(){
    int t=rr();
    while (t--) {
        init();
        std::vector v;
        ll ans=0;
        for(int i=1;i<=n;i++) {
            if(a[i]
                ll pos=lower_bound(all(v),a[i])-v.begin();
                ans+=pos;
            }
            if(a[i] 
E. Mirror Grid 
Problem - E - Codeforces
 
思路 
要求旋转90，180，270都相同，同一个位置上，只会出现四个不同的坐标，只要把这四个坐标上的值改成一样的就行。求出坐标之间的关系，取0和1数量的较小值作累加和。
 
#include 
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define debug(a) cout<<#a<<"="<ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const int maxn=1e2+6;

int n,m;
int a[maxn];
string s[maxn];
void init() {
    n=rr();
    for(int i=0;i
        cin>>s[i];
    }
}
int main(){
    int t=rr();
    while (t--) {
        init();
        int bx=n>>1;
        int ans=0;
        for(int i=0;i
            for(int j=0;j
                int one=0,ze=0;
                if(s[i][j]=='0') ze++;
                else one++;
                if(s[n-i-1][n-j-1]=='0') ze++;
                else one++;
                if(s[j][n-i-1]=='0') ze++;
                else one++;
                if(s[n-j-1][i]=='0') ze++;
                else one++;
                ans+=min(one,ze);
            }
        }
        if(n&1) {
            int i=bx;
            for(int j=0;j
                int one=0,ze=0;
                if(s[i][j]=='0') ze++;
                else one++;
                if(s[n-i-1][n-j-1]=='0') ze++;
                else one++;
                if(s[j][n-i-1]=='0') ze++;
                else one++;
                if(s[n-j-1][i]=='0') ze++;
                else one++;
                ans+=min(one,ze);
            }
        }
        std::cout << ans << 'n';
    }

}
 
D. Double Strings 
Problem - D - Codeforces
 
思路 
枚举长度然后看他存不存在就行。
 
#include 
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define debug(a) cout<<#a<<"="<ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const int maxn=1e5+6;

int n,m;
string s;
string sto[maxn];
int main(){
    int t=rr();
    while (t--) {
        n=rr();
        set a[10];
        for(int i=1;i<=n;i++) {
            cin>>s;
            int sz=s.length();
            a[sz].insert(s);
            sto[i]=s;
        }
        std::vector v;
        for(int i=1;i<=n;i++) {
            // sto[i]
            int sz=sto[i].length();
            bool fl=0;
            for(int len=1;len<=sz;len++) {
                int r=sz-len;
                if(a[r].empty() || a[len].empty()) continue;
                string tmp=sto[i].substr(0,len);
                string tt=sto[i].substr(len,r);
                if(a[len].count(tmp) && a[r].count(tt)){
                    fl=1;
                }
                if(fl) break;
            }
            v.pb(fl);
        }
        for(int i=0;i
            printf("%d",v[i]);
        }
        printf("n");
    }

}

                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！