2021济南站

J. Joy of Handcraft

关键点：并查集对于一段区间进行合并跳转的操作。

#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>
#define re register
using namespace std;
const int N =1e6+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int n,m,tax[N],f[N],ans[N],g;
struct node
{
    int t,x;
}e[N];
bool cmp(node n1,node n2)
{
    return n1.x>n2.x;
}
int r_find(int x)
{
    if(x==f[x]) return f[x];
    f[x]=r_find(f[x]);
    return f[x];
}
void solve()
{
    g++;
    memset(tax,0,sizeof tax);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>e[i].t>>e[i].x;
    sort(e+1,e+n+1,cmp);
    for(int i=0;i<=m;i++) f[i]=i,ans[i]=0;
    for(int i=1;i<=n;i++)
    {
        int t=e[i].t,x=e[i].x;
        if(tax[t]) continue;
        tax[t]=1;
        for(int j=1;j<=m;j+=2*t)
        {
            for(int k=j;k<j+t&&k<=m;k++)
                if(ans[k]==0) ans[k]=x,f[k-1]=k;
                else k=r_find(k);
        }
    }
    cout<<"Case #"<<g<<":";
    for(int i=1;i<=m;i++)
        cout<<" "<<ans[i];
    cout<<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

K. Knowledge is Power

打表找规律写的，数理基础不好。。。
打表：

int n,ans;
vector<int>e;
int check()
{
    for(int i=0;i<e.size();i++)
        for(int j=i+1;j<e.size();j++)
            if(__gcd(e[i],e[j])!=1)
                return 0;
    return 1;
}
void dfs(int pos,int val,int n)
{
    if(val>n) return;
    if(val==n)
    {
        if(check())
        {
            int mi=inf,mx=0;
            for(int i=0;i<e.size();i++)
                mi=min(mi,e[i]),mx=max(mx,e[i]);
            ans=min(ans,mx-mi);
        }
        return;
    }
    for(int i=pos+1;i<n;i++)
    {
        val+=i;
        e.push_back(i);
        dfs(i,val,n);
        val-=i;
        e.pop_back();
    }
}
void solve()
{
    for(int i=5;i<=100;i++)
    {
        ans=inf;
        if(i%2==0&&(i/2)%2)
        {
            e.clear();
            dfs(1,0,i);
            cout<<i<<" "<<ans<<endl;
        }
    }
}
signed main()
{
    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

ac代码：

#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>
#define re register
using namespace std;
const int N =1e6+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int x,g;
map<int,int>mp;
void solve()
{
    cin>>x;
    cout<<"Case #"<<g<<": ";
    if(x%2)
    {
        int x1=x/2,x2=x/2+1;
        cout<<1<<endl;
    }
    else if(x%2==0&&(x/2)%2==0)
    {
        cout<<2<<endl;
    }
    else if(x%2==0&&(x/2)%2)
    {
        if(x/2==3)
        {
            cout<<-1<<endl;
        }
        else
        {
            int tmp=((x-6)/4)%9;
            cout<<mp[tmp]<<endl;
        }
    }
}
signed main()
{
    mp[1]=3;mp[2]=4;mp[3]=2;mp[4]=4;
    mp[5]=3;mp[6]=2;mp[7]=3;mp[8]=3;
    mp[0]=2;
    //ios;
    int T;
    cin>>T;
    while(T--)
    {
        g++;
        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

C - FF

复习了一下set中find函数的用法，时间复杂度为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>
#define re register
using namespace std;
const int N =1e6+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int n,q;

void solve()
{
    cin>>n>>q;
    map<int,set<int>>mp;
    while(q--)
    {
        int op,x,y;cin>>op;
        if(op==1)
        {
            cin>>x>>y;
            mp[x].insert(y);
        }
        else if(op==2)
        {
            cin>>x>>y;
            mp[x].erase(y);
        }
        else
        {
            cin>>x>>y;
            int f1=0,f2=0;
            if(mp[x].find(y)!=mp[x].end()) f1=1;
            if(mp[y].find(x)!=mp[y].end()) f2=1;
            if(f1&&f2)
            {
                cout<<"Yes"<<endl;
            }
            else cout<<"No"<<endl;
        }
    }
}
signed main()
{
    ios;
    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

J Determinant

1.首先要根据公式推出来，矩阵行列式只受对角线元素影响。如果数理基础好一眼看出。。
2.本题的一个关键点。对大数的取模化简，不能使用double，可能会爆，还受精度影响。
3.高斯消元，保证对角线上的元素不为0.行变换注意将矩阵前加一个负号。

#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>
#define re register
using namespace std;
const int N =7e2+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,a[105][105],ans;
string s;
int fun(string s)
{
    int res=0;
    for(int i=0;i<s.length();i++)
        res=(res*10+(s[i]-'0'))%mod;
    return res;
}
int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int gauss()
{
    int tmp=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(a[i][j])
            {
                for(int k=1;k<=n;k++)
                    swap(a[i][k],a[j][k]);
                if(i!=j) tmp=tmp*(-1);
                break;
            }
        }
        for(int j=i+1;j<=n;j++)
        {
            int inv=getinv(a[i][i]);
            int g=a[j][i]*inv%mod;
            for(int k=1;k<=n;k++)
                a[j][k]=(a[j][k]-a[i][k]*g%mod+mod)%mod;
        }
        tmp=(tmp*a[i][i]%mod+mod)%mod;
    }
    return tmp;
}
void solve()
{
    cin>>n>>s;
    int g=fun(s);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
    int ans=gauss();
    if(ans==g)
        cout<<"+"<<endl;
    else
        cout<<"-"<<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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

D Arithmetic Sequence

#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>
#define re register
using namespace std;
const int N =7e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}

void print(__int128 x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int n,a[N];
__int128 b[N];
int Cal(int x)
{
    for(int i=1;i<=n;i++)
        b[i]=a[i]-(i-1)*x;
    nth_element(b+1,b+(n+1)/2,b+n+1);
    int med=b[(n+1)/2];
    __int128 tmp=0;
    for(int i=1;i<=n;i++)
    {
        __int128 g=med+(i-1)*x-a[i];
        if(g>0) tmp+=g;
        else tmp-=g;
    }
    return tmp;
}
bool check(int x,int y)
{
    int s1=Cal(x);
    int s2=Cal(y);
    if(s1<=s2) return 1;
    else return 0;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=-1e13,r=1e13,x,y;
    while(l<r)
    {
        x=l+(r-l)/3;
        y=r-(r-l)/3;
        if(check(x,y))
            r=y-1;
        else
            l=x+1;
    }
    cout<<Cal(l)<<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
64
65
66
67
68
69
70
71
72
73
74
75
76
77