树形模拟+随机函数+二分

Tree Constructer

本题成功看了我3个小时。少加了LL，导致位运算直接爆int了，还以为开了define int long long就没事了

#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 =1e2+5;
const int inf=1e18;
const int mod=1e9+7;
int n,col[N],p[N],num[5],id,pos[N];
vector<int>e[N];
int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=res*x;
        x=x*x;
        y>>=1;
    }
    return res;
}
void dfs(int u,int fa,int color)
{
    col[u]=color;
    num[color]++;
    for(int v:e[u])
    {
        if(v==fa) continue;
        dfs(v,u,3-color);
    }
}
void solve()
{
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0,1);
//    for(int i=1;i<=n;i++)
//        cout<
//    cout<
    id=2;
    if(num[1]>=num[2])
    {
        for(int i=1; i<=n; i++)
            if(col[i]==2)
                p[i]=qpow(2,60)-1-(qpow(2,id)+2),pos[i]=id,id++;
    }
    else
    {
        for(int i=1; i<=n; i++)
            if(col[i]==1)
                p[i]=qpow(2,60)-1-(qpow(2,id)+2),pos[i]=id,id++;
    }
//    for(int i=1;i<=n;i++)
//    {
//        if(p[i])
//        {
//            cout<
//            bitset<60>b(p[i]);
//            cout<
//        }
//    }
    for(int i=1; i<=n; i++)
    {
        if(!p[i])
        {
            int g=2;
            for(int j:e[i])
            {
                g+=(1ll<<pos[j]);
            }
            p[i]=g;
        }
    }
    for(int i=1; i<=n; i++)
    {
        cout<<p[i]<<" ";
//        bitset<60>b(p[i]);
//        cout<
    }
    cout<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
    solve();
    return 0;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
*/

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

B. Subway Pursuit

本来只是想写一道交互题。没想到找到到个2100的题，还看到了一个这么玄学的解法。
思路：
先二分枚举区间。不断缩小区间，直到区间的距离在认为给定的4k范围内，在利用随机函数生成区间中的点一次次尝试，直到找到火车位置。妙啊

#include
#define int long long
#define endl '\n'

using namespace std;
const int mod=1e4+7;
const int inf=1e18;
const int N=1e4+5;
int n,k,p;
string s;

void solve()
{
    cin>>n>>k;
    srand(time(0));
    int l=1,r=n;
    while(1)
    {
        if(r-l<=4*k)
        {
            int ans=rand()%(r-l+1)+l;
            cout<<ans<<" "<<ans<<endl;
            cin>>s;
            if(s=="Yes"||s=="Bad") return;
            else
            {
                l=max(1ll,l-2*k);r=min(n,r+2*k);
            }
        }
        else
        {
            int mid=(l+r)/2;
            cout<<l<<" "<<mid<<endl;;
            cin>>s;
            if(s=="Bad") return;
            if(s=="Yes")
            {
                l=max(1ll,l-k);r=min(n,mid+k);
            }
            else
            {
                l=max(1ll,mid+1-k);r=min(n,r+k);
            }
        }
    }
}
signed main()
{
    //cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    //int T;cin>>T;
    //while(1)
    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

C. Corrupted Sort

由于数据范围不大，只需要不停的输出数字去交换就可以

#include
#define int long long
#define endl '\n'

using namespace std;
const int mod=1e4+7;
const int inf=1e18;
const int N=1e4+5;
int n,flag;
string s;
void fun(int i,int j)
{
    cout<<i<<" "<<j<<endl;
    cin>>s;
    if(s=="WIN")
        exit(0);
}
void solve()
{
    cin>>n;
    while(1)
    {
        for(int i=1;i<n;i++) fun(i,i+1);
        for(int j=n;j>1;j--) fun(j-1,j);
    }
}
signed main()
{
    //cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    //int T;cin>>T;
    //while(1)
    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

Problem C. The Battle of Chibi

本来是nnm的dp写法，用树状数组优化后复杂度为O(m*n*log(n))

#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 =1e3+5;
const int inf=1e18;
const int mod=1e9+7;
int n,m,a[N],b[N],tr[N],dp[N][N],g;
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]=(tr[i]+x)%mod;
}
int ask(int tr[],int u)
{
    int res=0;
    for(int i=u;i>0;i-=lowbit(i)) res=(res+tr[i])%mod;
    return res;
}
void solve()
{
    g++;
    cin>>n>>m;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=0;
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+len+1,a[i])-b+1;
    //for(int i=1;i<=n;i++) cout<
    dp[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        memset(tr,0,sizeof tr);
        if(i==1) add(tr,1,dp[0][0]);
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=ask(tr,a[j]-1);
            add(tr,a[j],dp[i-1][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[m][i])%mod;
    cout<<"Case #"<<g<<": "<<ans<<endl;
}
signed main()
{
    ios;
    int T;cin>>T;
    while(T--)
        solve();
	return 0;
}
/*
2
3 2
1 2 3
3 2
3 2 1
*/

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
64
65