Dewy-Wiki

杭电杯第二场

ClearDewy大约 5 分钟

杭电杯第二场

个人题解，欢迎指正

P1002

思路：

签到题，将"std::make_tuple"去掉后输出后输出就行了

Code：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

string c="std::make_tuple";
string s;

void Qingtuan(){
    cin>>s;
    for (int i = 0; i < s.size(); i++)
    {
        if(i+15>s.size())break;
        if(string(s.begin()+i,s.begin()+i+15)==c){
            s.erase(s.begin()+i,s.begin()+i+15);
        }
    }
    cout<<s<<endl;
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    WA
}

P1003

题目大意：

  • 对于复制操作，选取区间[l,r][l,r]复制后插入到rr后面的位置

  • 对于询问操作，查询到结果后用个数字记录异或值总和

Codeforce上有道题类似：Problem - C - Codeforcesopen in new window

思路：

记录每次操作后此时字符串复制的[l,r][l,r]区间和总长度(若复制[2,4][2,4]则[l,r][l,r]为[5,7][5,7])，然后向前一个字符串映射，设询问的下标为idxidx

  • 若idx<lidx<l,则直接映射到前一个字符串
  • 若idx>ridx>r,在前一个字符串中该字符的位置为idx−(r−l+1)idx-(r-l+1)
  • 若l≤idx≤rl \leq idx \leq r,则idx=idx−c−r+lidx=idx-c-r+l,化简后的，自己尝试推一下

一直映射到最初的字符串就可以了

当然这不是正解，因为对于相同的查询的值异或为00，标程是用bitsetbitset优化，这里给出本人赛时代码

Code:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

ll n,q;
ll res=0;

void Qingtuan(){
    n=read();q=read();res=0;
    vector<ll>a(n+1);
    for (int i = 1; i <= n; i++)
    {
        a[i]=read();
    }
    vector<ll>b;
    vector<pair<ll,ll>>c;
    b.push_back(n);
    c.push_back({1,n});
    pair<ll,ll>t;
    int ch;ll k,idx;
    while (q--)
    {
        ch=read();
        if(ch==1){
            t.first=read();t.second=read();
            b.push_back(*b.rbegin()+t.second-t.first+1);
            c.push_back({t.second+1,t.second+1+t.second-t.first});
        }else{
            k=read();
            for (int i = b.size()-1; i >0; i--)
            {
                if(k<c[i].first)continue;
                if(k>c[i].second){
                    k-=c[i].second-c[i].first+1;
                }else{
                    k=k-1-c[i].second+c[i].first;
                }
            }
            res^=a[k];
        }
    }
    writ(res);ptn;


}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    WA
}

P1007

emm,本人没看这题，就直接贴上队友的代码了

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x)   ((x)&(-x))
#define fi first
#define se second
#define pb push_back
#define cf(_) int _;cin >> _;while(_--)

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
	int f = 1; x = 0; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	x *= f;
}

int main()
{
	IOS;
	cf(_)
	{
		int n;
		cin >> n;
		vector<pii> a(n);

		for(int i = 0;i < n;i++)	cin >> a[i].fi >> a[i].se;

		sort(a.begin(),a.end());
		// for(int i = 0;i < n;i++)	cout << a[i].fi << " " << a[i].se << endl;
		int res = 1;
		for(int i = 0;i < n - 1;i++)
		{
			if(a[i].se >= a[i + 1].fi)	
			{
				res -= 1;
				break;
			}	
			else	res++;
		}
		cout << res << endl;
	}
	return 0;
}

P1009

题目大意

给定P,Q,xP,Q,x满足：P × Q≡1 mod M，M为质数

判断是否有yy满足：x = y × P mod M

​ y = x × Q mod M

思路：

因为M为质数，且M最大为 P × Q-1，所以我们只需要将P × Q-1质因数分解，然后求出是否有这个 y 就可以了

Code：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

const int pri =2e6;
bool visi[pri+5];
int prime[pri+5];
int num = 0;

void getprime() {
    for (int i = 2; i <= pri; i++)
    {
        if (!visi[i])
        {
            prime[num++] = i;
        }
        for (int j = 0; j < num && i * prime[j] <= pri; j++)
        {
            visi[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
            break;
            }
        }
    }
}

ll p,q,x,y;
ll m;


void Qingtuan(){
    p=read();q=read();x=read();
    m=p*q-1;
    bool ju=0;
    for (int i = 0; i < num; i++)
    {
        if(!(m%prime[i])){
            while (!(m%prime[i]))
            {
                m/=prime[i];
            }
            y=x*q%prime[i];
            if(x==y*p%prime[i]){
                ju=1;break;
            }
        }
    }
    if(m!=1){
        y=x*q%m;
        if(x==y*p%m){
            ju=1;
        }
    }
    if(ju){
        writ(y);ptn;
    }else{
        puts("shuanQ");
    }


}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);
    getprime();
    int T=read();while (T--)
    Qingtuan();
    WA
}

P1012

题目大意：

有面值为7,31,365的三种硬币使用最小的硬币数量凑成总价值为 n ，求是否能凑成或最小硬币数

思路：

我们发现7和31互质，对于两个互质的数a，b，最大不能组成的数为a*b-a-b，此题为217，所以当n很大时，我们直接取模365，判断是否有解，如果没有，在n原本大于365的情况下，取模后加上一个365，此时必定有解，暴力枚举后输出即可

比赛的时候卡了好久，标程是dp枚举较小的，我这边直接暴力哈哈哈哈啊哈哈

Code：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}

ll n,m;


void Qingtuan(){
    n=read();
    bool ju=0;
    ll res=n/365;
    m=n%365;
    ll x,y=0;
    for (int i = 0; i < 20&&31*i<=m; i++)
    {
        if(!((m-31*i)%7)){
            y=i;ju=1;
        }
    }
    if(ju){
        x=(m-31*y)/7;
        writ(res+y+x);ptn;
        
    }else{
        if(res){
            m+=365;res--;
            for (int i = 0; i < 20&&31*i<=m; i++)
            {
                if(!((m-31*i)%7)){
                    y=i;
                }
            }
            x=(m-31*y)/7;
            writ(res+y+x);ptn;

        }else
            puts("-1");
    }


}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    WA
}
版权 @2022 清漙
Copyright © 2024 ClearDewy