LGR-147-Div.3】洛谷网校 7 月普及组月赛 & yLOI2022 总结-526互联

Upd：2023/8/5补

T1

普及组的题，而且T1，而且叫签到题。所以非常简单，入门难度。没什么好说的。
就是统计大写，小写和字母个数。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100+5;
string s;
int main(){
	cin>>s;
	int x=0,y=0,z=0;
	for(int i=0;i<s.size();i++){
		if(isdigit(s[i]))x++;
		else if(islower(s[i]))y++;
		else if(isupper(s[i]))z++;
	}
	cout<<x<<' '<<y<<' '<<z<<endl;
	return 0;
}

用时：1min43s

T2

题目看上去复杂，实则不难，就是给出\(n\)个\(m+1\)长度的等比数列，第\(i\)个数列的公比为\(i\)，首项为\(a_i\)，然后将他们按字典序排列（即找到第一个不相同的数位，比较大小）后，从小到大输出。

根据题目，我们略加思考就知道，首项不同，比首项即可；首项相同，看\(i\)即可：当首项都大于零，\(i\)越小，这个数列越小；当首项都小于零，\(i\)越大，这个数列越小。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000000+5;
int n,m;
ll ans[N];
struct node{
	int i;
	int k;
}a[N];
bool cmp(node x,node y){
	if(x.k!=y.k)return x.k<y.k;
	else{
		if(x.k<0)return x.i>y.i;
		else return x.i<y.i;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].k;
		a[i].i=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)cout<<a[i].i<<' ';
	return 0;
}

用时：50min38s

T4

题目描述很简洁，不加以解释。很明显，暴力可做，但是一定不是满分（讲个笑话，暴力能到80pts）

比赛时，手玩几个样例，可以发现，两个数时，一定成立。多个数时，必须让他们两两互质，才能成立。互质可以用\(log_2N\)的方法找因数并标记。这样做，其实是\(96Pts\)，但是!!!本人比赛就少了一段代码如下：
ll k=a[i]; if(S.count(k)){ f=1; cout<<"No"<<endl; break; }
自身判断忘了，所以\(96Pts->36Pts\)，还没别人暴力+乱搞的分多（乱搞能\(100Pts\)...)

96分代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500000+5;
ll T;
ll n;
ll a[N];
set<ll> S;
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		S.clear();
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(n==2){
			cout<<"Yes"<<endl;
		}else{
			bool f=0;
			for(int i=1;i<=n;i++){
				ll k=a[i];
				if(S.count(k)){
					f=1;
					cout<<"No"<<endl;
					break;
				} 
				S.insert(k); 
				for(int i=2;i<=sqrt(k);i++){
					if(k%i==0){
						if(S.count(i)||S.count(k/i)){
							f=1;
							cout<<"No"<<endl;
							break;
						}else{
							S.insert(i);
							S.insert(k/i);
						}
					}
				}
				if(f)break;
			}
			if(!f)cout<<"Yes"<<endl;
		}
	} 
	return 0;
}

赛时\(36Pts\)，用时2h42min33s。