2022“杭电杯”中国大学生算法设计超级联赛（2）签到题5题

Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Static Query on Tree 18.85% (217/1151)
1002 C++ to Python 75.33% (1081/1435)
1003 Copy 19.23% (323/1680)
1004 Keychains 12.15% (52/428)
1005 Slayers Come 25.91% (64/247)
1006 Bowcraft 20.65% (38/184)
1007 Snatch Groceries 36.68% (914/2492)
1008 Keyboard Warrior 11.87% (78/657)
1009 ShuanQ 23.90% (730/3055)
1010 Assassination 24.06% (32/133)
1011 DOS Card 24.59% (165/671)
1012 Luxury cruise ship 33.43% (895/2677)

B. C++ to Python

C++ to Python
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 19 Accepted Submission(s): 17

Problem Description
Kayzin’s repository has lots of code in C++, but Aba aba can only understand Python code. So Aba aba calls you for help.

The only things you should do is using (…) in Python to match std::make_tuple(…) in C++.

Input
First line has one integer T, indicates T test cases. In each case:

First line has string s, indicates C++ code.

The C++ code only contains std::make_tuple, “(”, “)”, “,” and integers, without space.

1≤T≤100, the length of s not exceeds 1000.

Output
Each test cases print one line of Python code, do not print any space.

Sample Input
2
std::make_tuple(-2,3,3,std::make_tuple(3,3))
std::make_tuple(std::make_tuple(1,1,4,5,1,4))

Sample Output
(-2,3,3,(3,3))
((1,1,4,5,1,4))

题意：

• 输入一个字符串，去掉std::make_tuple后输出。

思路：

• 遇到std::make_tuple里面有的字符就不输，其他的就原样输出即可。

#include
using namespace std;

int main(){
    string t = "std::make_tuple";
    set<char>se;
    for(int i = 0; i < t.size(); i++)se.insert(t[i]);
    int T;  cin>>T;  cin.get();
    while(T--){
        string s;  getline(cin,s);
        for(int i = 0; i < s.size(); i++){
            if(!se.count(s[i]))cout<<s[i];
        }
        cout<<"\n";
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

L. Luxury cruise ship

Luxury cruise ship
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 83 Accepted Submission(s): 21

Problem Description
Kayzin plans to buy a luxury cruise ship which will cost N coins. But Kayzin didn’t have enough coins, so Kayzin decided to start saving coins.

Kayzin will put 7 or 31 or 365 coins into his piggy bank each day. Now Kayzin wants to know at least how many days he will need to “exactly”(No more and no less) scrape together the money for buying a luxury cruise.

If Kayzin can’t “exactly” scrape together the money for buying a luxury cruise, print -1.

Input
The first line contains an integer T(T≤1000) . Then T test cases follow.

For one case, the first line contains an integer N (1≤N≤1018) , N denotes the coins that a luxury cruise ship will cost.

Output
Print an integer for each case, indicating the minimum number of days Kayzin needs.

If Kayzin can’t “exactly” scrape together the money for buying a luxury cruise, print -1.

Sample Input
5
14
38
55
403
996

Sample Output
2
2
-1
3
16

题意：

• 求用最少的7 或 31 或 365 ，表示给出的数字N（1e18）。

思路：

• 对于小于1e6的情况，就是个硬币问题，可以直接类似于背包的做法O(n)去dp。
• 对于大于1e6的情况，可以直接用365把他们减到1e6以下。
• 注意要数组要开的比1e6大一点（直接上2e6），不然会WA。

#include
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const LL maxn = 2e6+10;
const LL inf = 2e18+10;

LL c[] = {7, 31, 365};
LL f[maxn] = {0};

int main(){
    IOS;
    for(LL i = 1; i < maxn; i++)f[i] = inf;
    LL m = 3;
    for (LL j = 1; j < maxn; j++){ //f[i]到i为止最少用多少硬币
        for (LL i = 0; i < m; i++)
            if (j - c[i] >= 0)
                f[j] = min(f[j], f[j - c[i]] + 1);
    }
    LL T;  cin>>T;
    while(T--){
        LL x;  cin>>x;
        LL sum = 0;
        if(x > (LL)1e6){
            sum = (x-1e6)/365+1, x -= sum*365;
        }
        if(f[x]!=inf)cout<<f[x]+sum<<"\n";
        else cout<<"-1\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

G. Snatch Groceries

Problem Description
“SNATCH GROCERIES first, then get a covid test” has quickly become an anthem for the lockdown that started suddenly in Shanghai in the early hours of March 28th. We can describe scenes of panic buying—qiang cai, or snatching groceries—and the threat of being locked out of one’s home amid a frenzied bid to control an outbreak of covid-19 in China’s main business and finance hub. Here is the question, how does the server determine who succeeded When millions of people press the order button on their mobile phones at the same time.

Processing such a large number of requests requires a distributed system. In a distributed system, time is a tricky business, because communication is not instantaneous: it takes time for a message to travel across the network from one machine to another. The time when a message is received is always later than the time when it is sent, but due to variable delays in the network, we don’t know how much later. This fact sometimes makes it difficult to determine the order in which things happened when multiple machines are involved

Moreover, each machine on the network has its own clock, which is an actual hardware device: usually a quartz crystal oscillator. These devices are not perfectly accurate, so each machine has its own notion of time, which may be slightly faster or slower than on other machines. It is possible to synchronize clocks to some degree: the most commonly used mechanism is the Network Time Protocol (NTP), which allows the computer clock to be adjusted according to the time reported by a group of servers. The servers in turn get their time from a more accurate time source, such as a GPS receiver.

Modern computers have at least two different kinds of clocks: a time-of-day clock and a monotonic clock. A time-of-day clock does what you intuitively expect of a clock: it returns the current date and time according to some calendar (also known as wall-clock time). For example, clock_gettime(CLOCK_REALTIME) on Linux return the number of seconds (or milliseconds) since the epoch: midnight UTC on January 1, 1970, according to the Gregorian calendar, not counting leap seconds. Some systems use other dates as their reference point. Time-of-day clocks are usually synchronized with NTP,

You may be able to read a machine’s time-of-day clock with microsecond or even nanosecond resolution. But even if you can get such a fine-grained measurement, that doesn’t mean the value is actually accurate to such precision. In fact, it most likely is not—as mentioned previously, the drift in an imprecise quartz clock can easily be several milliseconds, even if you synchronize with an NTP server on the local network every minute. With an NTP server on the public internet, the best possible accuracy is probably to the tens of milliseconds, and the error may easily spike to over 100 ms when there is network congestion.

Thus, it doesn’t make sense to think of a clock reading as a point in time—it is more like a range of times, within a confidence interval: for example, a system may be 95% confident that the time now is between 10.3 and 10.5 seconds past the minute, but it doesn’t know any more precisely than that. If we only know the time +/– 100 ms, the microsecond digits in the timestamp are essentially meaningless.

An interesting exception is Google’s TrueTime API in Spanner, which explicitly reports the confidence interval on the local clock. When you ask it for the current time, you get back two values: [earliest, latest], which are the earliest possible and the latest possible timestamp. Based on its uncertainty calculations, the clock knows that the actual current time is somewhere within that interval. The width of the interval depends, among other things, on how long it has been since the local quartz clock was last synchronized with a more accurate clock source.

TL;DR: Spanner implements snapshot isolation across data centers in this way. It uses the clock’s confidence interval as reported by the TrueTime API, and is based on the following observation: if you have two confidence intervals, each consisting of an earliest and latest possible timestamp (A=[Aearliest,Alatest],B=[Bearliest,Blatest]), and those two intervals do not overlap (i.e.,Aearliest

Now we use Spanner as a solution, there are millions of people snatching groceries, and everyone is given the clock’s confidence interval. The server executes each request in chronological order, and terminate in case of intervals overlap. Here is the question, how many people can get their food before the server is terminated.

Input
First line has one integer T, indicating there are T test cases. In each case:

First line has one integers n, indicating there are n people.

For next n lines, each line has 2 integers earliest,latest, indicates the clock’s confidence interval.

T≤10,1≤n≤105,0≤earliesti

Output
In each case, print one integer, indicates the answer.

Sample Input
2
3
1 2
3 4
5 6
3
1 2
2 3
1 5

Sample Output
3
0

题意：

• 给出n个区间，按照l排序，求从左到右有多少个区间不重叠。

思路：

• 直接输入区间排个序，然后维护当前最右端点与下个区间的左端点做判断即可。
• 如果相邻break出去了就要-1，减掉重叠的区间，全部都不冲突就不用减。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 1e6+10;
struct node {int l, r; }a[maxn];
bool cmp(node x, node y){ return x.l<y.l; }
int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 1; i <= n; i++)cin>>a[i].l>>a[i].r;
        sort(a+1,a+n+1,cmp);
        int lst = a[1].r, cnt = 1, ff = 0;
        for(int i = 2; i <= n; i++){
            if(a[i].l>lst){
                cnt++;
            }else{
                ff = 1;
                break;
            }
            lst = max(lst, a[i].r);
        }
        cout<<cnt-ff<<"\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

I. ShuanQ

ShuanQ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 167 Accepted Submission(s): 56

Problem Description
CX is a programmer of a mooc company. A few days ago, he took the blame for leakage of users’ data. As a result, he has to develop an encryption algorithm, here is his genius idea.

First, the protocol specifies a prime modulus M, then the server generates a private key P, and sends the client a public key Q. Here Q=P−1,P×Q≡1modM.

Encryption formula: encrypted_data=raw_data×PmodM

Decryption formula: raw_data=encrypted_data×QmodM

It do make sense, however, as a master of number theory, you are going to decrypt it.You have intercepted information about P,Q,encrypted_data, and M keeps unknown. If you can decrypt it, output raw_data, else, say “shuanQ” to CX.

Input
First line has one integer T(T≤20), indicating there are T test cases. In each case:

One line has three integers P,Q,encrypted_data. (1

It’s guaranteed that P,Q,encrypted_data

Output
In each case, print an integer raw_data, or a string “shuanQ”.

Sample Input
2
5 5 5
6 6 6

Sample Output
shuanQ
1

Source
2022“杭电杯”中国大学生算法设计超级联赛（2）

题意：

• 已知一个加解密方案：
  en=raw×P%mod ， raw=enxP%mod
  PQ互为逆元， mod为素数， P,Q,en
• 给出P, Q, en，求raw的值。

思路：

• 因为互为逆元，所以PQ-1%mod=0，即PQ-1=kmod。
  mod是一个比P和Q都大的（PQ-1）的质因子。
  可以证明最多只有一个这样的质因子。
• 因此枚举PQ-1的质因子，然后判断是否都大于p,q即可。
  质因子枚举+素数试除法即可。
  当时写了线性筛然而发现并不用。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL mod = 1e9+7;
const LL maxn = 3e6+10;

//线性筛
LL vis[maxn], primes[maxn], cnt;
void get_primes(LL n){
	for(LL i = 2; i <= n; i++){
		if(!vis[i])primes[++cnt]=i;
		for(LL j = 1; primes[j] <= n/i; j++){
			vis[primes[j]*i] = 1;
			if(i%primes[j]==0)break;
		}
	}
}
//判断素数
bool isprime(LL n){
	if(n<2)return false;
	for(LL i = 2; i <= n/i; i++){
		if(n%i==0)return false;
	}
	return true;
}

int main(){
    IOS;
	// get_primes(maxn-10);
    // vis[1] = 1;    
    int T;  cin>>T;
    while(T--){
        LL p, q, en;  cin>>p>>q>>en;
        LL mm = p*q-1, mmd = -1;
        LL sqm = sqrt(mm);
        for(LL i = 1; i <= sqm+1; i++){
            if(mm%i==0){
                if(isprime(i) && i>en && i>q && i>p){
                    mmd = i;  break;
                }
                if(mm>en*i && mm>q*i && mm>p*i && isprime(mm/i)){
                    mmd = mm/i; break;
                }
            }
        }
        if(mmd==-1){
            cout<<"shuanQ\n";
        }else{
            cout<<q*en%mmd<<"\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
53
54

C. Copy

Copy
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 283 Accepted Submission(s): 99

Problem Description
Kayzin has a list of integers, initially the list is a1,a2,…,an. He will execute q operations.

For an operation of first type, he will select an interval [li,ri], copy and insert it to the end of the interval.

For an operation of second type, he wonder the xi-th integer of the list.

You need to print the xor sum of all the answers of second type operations.

ps: What is xor? The xor value of two integers is equal to addition in binary without carry.

ps: n is a constant for each test case.

Input
First line is an integer T, indicating the number of test cases. For each test case:

First line is 2 integers n,q, indicating the length of initial list and the number of operations.

Next line is n integers a1,a2,…,an, indicating the initial list.

Next q line, one operation per line. The i-th line could be 3 integers (1,li,ri), indicating the first type operation, or 2 integers (2,xi), indicating the second type operation.

1≤T≤10, 1≤n,q≤105, 1≤ai≤109, ∑n≤105, ∑q≤105, 1≤xi,li,ri≤n, the sum of the number of first type operations (all test cases together) not exceeds 20000.

Output
For each test case, print one line, indicating the xor sum of the answers.

Sample Input
1
5 3
1 2 3 4 5
2 4
1 2 4
2 5

Sample Output
6

Hint
For first operation, the 4-th integer is 4.
For second operation, 2,3,4 is copied, the list becomes 1,2,3,4,2,3,4,5.
For third operation, the 5-th integer is 2.
So the result is 2 xor 4 = 6

Source
2022“杭电杯”中国大学生算法设计超级联赛（2）

题意：

• 长为n的数组，q次操作，询问第x个数或将区间[l,r]复制一份插在r的后面。
• n, q, x, l, r<1e5。

思路：

• 官方题解：
  
• 奇妙操作：因为某些原因，暴力和正解的差距并不是很大甚至暴力可以比正解还快。
• 比赛时： 注意到x<1e5，意味着超过n的部分都不要了。加上，操作1小于2e4，加上sumq和sumn<1e5，加上过了那么多人，要不暴力一发试试（（（

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 1e6+10;
int a[maxn];
int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n, q;  cin>>n>>q;
        for(int i = 1; i <= n; i++)cin>>a[i];
        int ans = 0;
        while(q--){
            int op;  cin>>op;
            if(op==1){
                int l, r;  cin>>l>>r;
                int len = r-l+1;
                for(int i = n; i >= r+1; i--)a[i] = a[i-len];
            }else{
                int x;  cin>>x;
                ans ^= a[x];
            }
        }
        cout<<ans<<"\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