杭州热身 思维训练

Problem B. Useful Algorithm

题意:交互题，有个分数的分子是x，分母是y，他们都大于等于1且不大于1000，每次询问会告诉你你猜的数是大还是小，请你用不超过20次的询问来才出来x和y，

思路：x和y一共可以组成不超过1e6组方案，并且可以按照大小去排序，然后就可以根据这个来二分出答案。

#include 

using namespace std;
#define int long long
const int N = 1e6+100;
const int up=1e3;
struct node
{
    int p,q;
    bool operator<(const node &a)const
    {
        return p*a.q<a.p*q;
    }
}b[N];
map<pair<int,int>,int>mp;
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n=0;
    for(int i=1;i<=up;i++)
    for(int j=1;j<=up;j++)
    {
        int p=j,q=i;
        int g=__gcd(p,q);
        p/=g;q/=g;
        if(!mp[{p,q}])
        {
            n++;
            b[n].p=p;
            b[n].q=q;
        }
        mp[{p,q}]=1;
    }
    sort(b+1,b+n+1);
    int l=1,r=n;
    for(int i=1;i<=20;i++)
    {
        int mid=l+r>>1;
        cout<<"compare "<<b[mid].p<<" "<<b[mid].q<<endl;
        char ch;cin>>ch;
        if(ch=='>') r=mid-1;
        else if(ch=='<') l=mid+1;
        else break;
    }
    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

A. AquaMoon and Two Arrays
边角情况注意

其他的倒是没什么

#include 

using namespace std;
#define int long long
const int N = 1e5+100;
int a[N];
int b[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        int suma=0;
        int sumb=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            suma+=a[i];
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>b[i];
            sumb+=b[i];
            cnt+=abs(b[i]-a[i]);
        }
        if(suma!=sumb)
        {
            cout<<-1<<endl;
            continue;
        }
        if(cnt&1)
        {
            cout<<-1<<endl;
            continue;
        }
        if(n==1&&cnt)
        {
            cout<<-1<<endl;
            continue;
        }
        vector<pair<int,int>>v;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>b[i])
            {
                for(int j=i+1;j<=n;j++)
                {
                    while(a[j]<b[j]&&a[i]>b[i])
                    {
                        v.push_back(make_pair(i,j));
                        a[j]++;
                        a[i]--;
                    }
                }
            }
            if(a[i]<b[i])
            {
                for(int j=i+1;j<=n;j++)
                {
                    while(a[j]>b[j]&&a[i]<b[i])
                    {
                        v.push_back(make_pair(j,i));
                        a[i]++;
                        a[j]--;
                    }
                }
            }
        }
        cout<<v.size()<<endl;
        for(auto x:v)
            cout<<x.first<<" "<<x.second<<endl;
    }
    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

B - AquaMoon and Stolen String

题意：给定n个字符串，n是奇数，里面有n/2对是重复的，现在会随机打乱这些重复的所有的字母，请你求出不重复的那个字符串。

思路：洛谷有个n个筷子选一个长度独特的筷子的题，和这个一样的。

#include
#include
#include
#include
#include
#include
#include
# include
# include
# include
# pragma optimize(2)
using namespace std;
typedef long long int ll;
char  ans[100000+10];
int main ()
{
   int t;
   cin>>t;
 
   while(t--)
   {
       int n,len;
       cin>>n>>len;
       getchar();
 
 
       string s;
       cin>>s;
 
       for(int i=0;i<len;i++)
       {
           ans[i]=s[i];
       }
 
       for(int i=2;i<=2*n-1;i++)
       {
           cin>>s;
 
           for(int i=0;i<len;i++)
           {
               ans[i]^=s[i];
           }
       }
 
       for(int i=0;i<len;i++)
       {
           cout<<ans[i];
       }
       cout<<'\n';
   }
    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

E. 睡觉
好题
长时间以来，我做过的关于循环数组的题都是只考虑一个循环就够了，那么这个题提醒我们要注意一个循环对于无线循环的影响，讨论多种情况。

#include 

using namespace std;

const int N = 1e6+100;
int a[N];
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int x,t,k,n,d;
        cin>>x>>t>>k>>n>>d;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i+n]=a[i]=a[i]<=d?-1:1;
        }
        bool falg=false;
        int len=0;
        int xx=x;
        for(int i=1;i<=n*2;i++)
        {
            x+=a[i];
            if(x<=k)
            {
                len++;
                if(len>=t)
                {
                    falg=true;
                }
            }
            else
            {
                len=0;
            }
        }
        if(x<xx)
        {
            falg=true;
        }
        else if(x==xx&&(len==n*2)&&t>=n*2)
            falg=true;
        if(falg)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    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

B. GCD Problem

题意：把一个数n拆成a,b,c，然后要求gcd(a,b)=c

思路：认定ab互质，然后暴力查找

#include
using namespace std;
int main() {
	int t;
	cin >> t;
	while (t--) {
		int a;
		cin >> a;
		a--;
		int b = a / 2;
		while (b == a - b || __gcd(b, a - b) > 1) b--;
		cout << a - b << " " << b << " " << 1 << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

数论题也能暴力找？？
再来一个之前做过的辽宁省赛的题
https://ac.nowcoder.com/acm/contest/43937/F

#include
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5+100;
int a[N];
const int mod = 1e9+7;
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        int ans=0;
        cin>>n;
        if(n&1ll)
        {
            ans=n/2;
        }
        else
        {
            int temp=n/2;
            if(temp&1)
            {
                ans=n/2-2;
            }
            else
            {
                ans=n/2-1;
            }
        }
        if(ans>n/2||ans<n/4+(n%4!=0))
        {
            cout<<-1<<endl;
        }
        else
        {
            cout<<ans<<endl;
        }
    }
   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

剩下时间用来看之前的博客+复习了