第四届齐鲁校赛+二分思维+cf

奥特曼的时间管理

真的要被自己蠢死了！！如果想到差分，秒过的题！我花了几个小时调自己的贪心代码，边界怎么都分不对。
贪心的写法感觉是对的，就算是按照后边界排序，也不应该做不出来。
差分思路：气死我了，好蠢

#include
#define int  long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=2e6+5;
const int inf=1e18;
const int mod=998244353;
int n,x,y,z,k,val,f[N];

void solve()
{
    cin>>n>>x>>y>>z>>k>>val;
    int sum=x*y*z-1;
    for(int i=1;i<=n;i++)
    {
        string s1,s2;cin>>s1>>s2;
        int l=((s1[0]-'0')*10+s1[1]-'0')*y*z+((s1[3]-'0')*10+s1[4]-'0')*z+((s1[6]-'0')*10+s1[7]-'0');
        int r=((s2[0]-'0')*10+s2[1]-'0')*y*z+((s2[3]-'0')*10+s2[4]-'0')*z+((s2[6]-'0')*10+s2[7]-'0')+k;

        f[l]++,f[r+1]--;
    }
    for(int i=1;i<=sum;i++) f[i]+=f[i-1];
    int ans=0;
    for(int i=0;i<=sum;i++) if(f[i]>=1) ans++;
    cout<<ans*val<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while()
//    cout<<6*12*62+3*62+60<
//    cout<<6*12*62+4*62+21<
    solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

新大陆

这题属于被骗到了……哭
n*m的乘积小于1e6，此时我们没有办法开全局二维数组，但我们可以开局部二维数组！！
在main函数中开，然后memset初始化就可以了。
再开两个数组记录是否存在那样的矩阵，注意只要平行于x轴，可随意放置(只有2种)

#include
#define int  long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=2e6+5;
const int inf=1e18;
const int mod=998244353;
int n,m;

void solve()
{
    cin>>n>>m;
    int g[n+1][m+1],r[n+1][m+1],c[n+1][m+1];
    memset(g,-1,sizeof g);
    memset(r,0,sizeof r);memset(c,0,sizeof c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>g[i][j];
    int h,w;cin>>h>>w;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)
    {
        if(g[i][j-1]==g[i][j]) r[i][j]=r[i][j-1]+1;
    }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        if(g[i-1][j]==g[i][j]) c[i][j]=c[i-1][j]+1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        if(r[i][j]==h-1&&c[i][j]==w-1||r[i][j]==w-1&&c[i][j]==h-1)
        {
            cout<<"YES"<<endl;return;
        }
    }
    cout<<"NO"<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Leonard的子序列

状态转移+树状数组转移
思路：对于每一个数来说，可由小于等于它两倍的数结尾的数得到，再加上它的个数，这一部分便组合成每个子序列的长度，再加上1(本身)

#include
#define int  long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int n,a[N],b[N],tr[N],tr2[N],ans;

int lowbit(int x){return x&(-x);}
void add(int tr[],int u,int x)
{
    for(int i=u;i<N;i+=lowbit(i)) tr[i]+=x;
}
int sum(int tr[],int u)
{
    int res=0;
    for(int i=u;i>0;i-=lowbit(i)) res+=tr[i];
    return res;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
    {
        int id1=lower_bound(b+1,b+m+1,a[i]/2)-b;
        if(b[id1]>a[i]/2) id1--;
        int id2=lower_bound(b+1,b+m+1,a[i])-b;
        int p=sum(tr,id1),q=sum(tr2,id1);
        add(tr,id2,(p+q+1)%mod);
        add(tr2,id2,(q+1)%mod);
        ans=((ans+p)%mod+q+1)%mod;
    }
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

C. Number Game

思路：二分长度，check函数判断能否删去x个数。Alice会尽量删去大数，Bob会删去小数。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>

using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
int n,a[N],vis[N];
bool cmp(int a,int b){return a>b;}
bool check(int x)
{
    int l=1,r=n;
    for(int i=0;i<=100;i++) vis[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=x-l+1&&!vis[i])
        {
            vis[l++]=1;vis[r--]=1;
        }
    }
    return l>x;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,cmp);
    int l=0,r=(n+1)/2,mid,ans;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

G. Occupy the Cities

思路：开设前驱数组和后驱数组，记录每个0左方和右方最近的1.
二分枚举长度，二分策略还是挺明显的。尽量先使用左边的1

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>
using namespace std;
const int N =2e6+5;
const int inf=1e18;
int n,pre[N],ls[N],vis[N];
string s;
bool check(int x)
{
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1') continue;
        int g=min(i-pre[i],ls[i]-i)+1;
        if(g<=x) continue;
        if(i-pre[i]<=x&&!vis[pre[i]])
        {
            vis[pre[i]]=1;continue;
        }
        else if(ls[i]-i<=x&&!vis[ls[i]])
        {
            vis[ls[i]]=1;continue;
        }
        return 0;
    }
    return 1;
}
void solve()
{
    cin>>n>>s;s=" "+s;
    for(int i=0;i<=n+5;i++) pre[i]=ls[i];
    int x=-1e9;
    for(int i=1;i<=n;i++)
    {
        pre[i]=x;
        if(s[i]=='1') x=i;
    }
    x=inf;
    for(int i=n;i>=1;i--)
    {
        ls[i]=x;
        if(s[i]=='1') x=i;
    }
    int l=0,r=n,mid,ans;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--) solve();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63