第十一届"图灵杯"NEUQ-ACM程序设计竞赛

赛时水过了9题（含水量大，I题数据太差了）

古堡中的勇士

由于勇士一定会卡在两个人之间，所以只需要枚举这两部分的宝物

有宝物在就加加就行，很清晰

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
// 暴力枚举
#include <iostream>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
void solve()
{
ll a,b,c;
cin>>a>>b>>c;
ll n;
cin>>n;
ll ans=0;
rep(i,1,n)
{
    ll x;
    cin>>x;  
    if(x>b&&x<c)
    {
        ans++;
    }  
}
cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

三星五费

赛时一看读不懂直接跳了，打到一半发现不难，纯模拟

只需要留下5个金币去买就行

所以如果你连7个金币都没有，还是早早离场罢

如果你有，能不能抽到就看你是第一场抽到还是第二场还是第n场了，类似于几何分布去做就可以了。

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
const int N=550;
void solve()
{
int n;
cin>>n;
if(n<7)
{
    double ans=0;
    printf("%.3lf",ans);
}
else
{
  int t=(n-5)/2;
  double ans=0.03;
  double _sum=1;
  rep(i,2,t)
  {
    _sum *= 0.97;
    ans+=_sum*0.03;
}
printf("%.3f",ans);
}

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--)
    {
        solve();
    }
}

我就要不协调

感觉自己做的一坨，应该是没有这么复杂的

整体思路是先排序特判是不是0

然后找每个数后面比他大的数最小的那个数字，因为给他加到超过它就行了

然后就是枚举

注意一下细节就行

应该有不麻烦的做法，但笔者孱弱，想不出来

本来到这里就停了，突然发现比他大的数最小的数字不就是他下一个吗（）caole

多了一堆没用的。

后一份是修正后的

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
// 暴力枚举素数即可
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
const int N=550;
ll a[N];
ll minn;
ll b[N];
ll c[N];
void solve()
{
int n;
cin>>n;
cin>>a[1];
minn=a[1];
c[1]=a[1];
rep(i,2,n)
{
    cin>>a[i];
    c[i]=a[i];
}
bool flag=1;
sort(c+1,c+1+n);
rep(i,1,n)
{
    if(a[i]!=c[i])
    {
        flag=0;
        break;
    }
}
if(!flag)
{
cout<<'0'<<'\n';
}
else
{
rep(i,1,n)
{
    ll minn=1e10;
frep(j,n,i+1)
{
    if(a[j]>=a[i]&&minn>a[j])
    {
        b[i]=a[j];
        minn=a[j];
    }
}
}
//rep(i,1,n)
//{
  //  cout<<b[i]<<'\n';
//}

ll ans=1e10;
rep(i,1,n-1)
{
    if(b[i]!=1e10)
    {
        if(b[i]-a[i]==0)
        {
        ans=min(ans,1ll);
        }
        else if((b[i]-a[i])%2==1)
        {
        ans = min(ans, (b[i] - a[i]) / 2+1);
        }
        else
        {
        ans = min(ans, (b[i] - a[i]) / 2+1);
        }
    }
}
cout<<ans<<'\n';
}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//队内某大佬的，可以康康
void solve(){
    int n;
    cin >> n;
    ll ans=1e18;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    for(int i=2;i<=n;++i){
        if(a[i]<a[i-1]){
            ans=0;
            break;
        }
        else {
            ans=min(ans,(a[i]-a[i-1])/2+1);
        }
    }
    cout << ans << "\n";
     
}

古希腊掌管原神的神

1个真神就不需要问了

相等的话也问不出来

假神更多也问不出来

真神比假神多，那么你也要问完假神数量*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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a,b,c,d;
    cin>>a>>c>>d;
    b=c+d;
    if(a==1&&b==0)cout<<"YES"<<endl<<'0';
    else
    {
        if(a==b)cout<<"NO";
        else if(a>b)cout<<"YES"<<endl<<2*b+1;
        else cout<<"NO";
    }
    return 0;
}


字母匹配

这不是CF原题吗，本题很容易，不适合这个位置

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
#include <iostream>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
const int N=30;
int a[N];
int b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int t=s.length()-1;
    rep(i,0,t)
    {
if(s[i]>='a'&&s[i]<='z')
{
    a[int(s[i]-'a')]++;
}
else
{
    b[int(s[i]-'A')]++;
}
    }
    ll ans=0;
    ll res=0;
rep(i,0,25)
{
    ans+=min(a[i],b[i]);
res+=abs(a[i]-b[i])/2;
}
    if(res>=k)
    {
        cout<<ans+k<<'\n';
    }
    else 
{
    cout<<ans+res<<'\n';
}

}

数学家的四不选

偶数特判即可

质数先打出来

三角数也是

卡特兰数就那些

打出来就行

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
const int N = 1e6;
ll a[N];
ll minn;
ll b[N];
ll c[N];
int IsPrime(int n)
{
    int i;
    if (n < 2 || (n != 2 && n % 2 == 0))
        return 0;
    else
    {
        for (i = 3; i * i <= n; i += 2)
        {
            if (n % i == 0)
                return 0;
        }
        return 1;
    }
}
//质数筛，可以更优秀，但没必要
void solve()
{
    int sum=0;
rep(i,1,1e5)
{
    sum+=i;
    if(sum>1e5)
    {
        break;
    }
    a[sum] = 1;
}
    //特判数字和，可以考虑跳出优化
rep(i,1,1e5)
{
    if(IsPrime(i))
    {
        a[i]=1;
    }
}
    //特判质数
a[1]=1;
a[2]=1;
a[14]=1;
a[42]=1;
a[132]=1;
a[429]=1;
a[1430]=1;
a[4862]=1;
a[16796]=1;
a[58786]=1;
    //卡特兰数字
int n;
cin>>n;
int ans=0;
rep(i,1,n)
{
    //特判偶数
    if(!a[i]&&i%2)
    {
        ans++;
    }
}
cout<<ans<<'\n';



}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while (t--)
    {
        solve();
    }
}

旗鼓相当的对手

裸的01背包，因为就是凑sum/2这个背包最多凑多少

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
// 暴力枚举素数即可
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (ll i = a; i <= n; i++)
#define frep(i, a, n) for (ll i = a; i >= n; i--)
#define ll long long
const int N = 1e6;
ll a[N];
ll f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    ll sum=0;
    rep(i,1,n)
    {
        cin>>a[i];
        sum+=a[i];
    }
  rep(i,1,n)
        for (ll k = sum/2; k >= a[i]; k--)
            f[k] = max(f[k], f[k - a[i]] + a[i]);
    cout << sum-2*f[sum/2];
    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
// 暴力枚举素数即可
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (ll i = a; i <= n; i++)
#define frep(i, a, n) for (ll i = a; i >= n; i--)
#define ll long long
const int N = 1e6;
ll a[N];
ll b[N];
set<ll>q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 int n,m;
 cin>>n>>m;
 rep(i,1,n)
 {
    cin>>a[i];
 }
rep(i,1,m-1)
{
    a[i]-=a[m];
}
    //还差他们多少分
 rep(i,1,n)
 {
    cin>>b[i];
 }
rep(i,2,n)
{
    b[i]=b[1]-b[i];
}
    //能够拿来追回他们多少分
int j=2;
    //从第二个开始给，肯定是越少越优秀，越多分要留给越难对付的对手
int cnt=0;
frep(i,m-1,1)
{
while(b[j]<a[i]&&j<=n)
{
j++;
    //枚举
}
if(b[j]>=a[i])
{
cnt++;
    //确实比他大就记录
j++;
}
}
cout<<m-cnt<<"\n";


}

字符比较

这不是正解，数据水（）

这样都能过

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (ll i = a; i <= n; i++)
#define frep(i, a, n) for (ll i = a; i >= n; i--)
#define ll long long
const int N = 1e6;
ll a[N];
ll b[N];
set<ll> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    string s1, s2;
    cin >> s1 >> s2;
    rep(i, 1, q)
    {
        int l1, l2, r1, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int len1=r1-l1+1;
        int len2=r2-l2+1;
        string t1=s1.substr(l1-1,len1);
        string t2=s2.substr(l2-1,len2);
        if(t1<t2)
        {
            cout<<'<'<<'\n';
        }
        else if(t1>t2)
        {
            cout<<'>'<<'\n';
        }
        else
        {
            cout<<'='<<'\n';
        }
    }
    return 0;
}