模板:
欧几里得算法
//若a,b互质则返回1,否则返回0
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}题目:
AcWing 1360. 有序分数
暴力模拟法(AC):
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n;
typedef pair<int,int>pii;
pii num[100005];
bool cmp(pii a,pii b){
return a.x*b.y<a.y*b.x;
}
int main(){
//输入
cin>>n;
//暴力枚举每一种分数的情况(肯定有重复的可能)
int k=0;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
num[k].x=j;
num[k].y=i;
k++;
}
}
//暴力去重,并且利用1/1进行标记
int cnt=0;
for(int i=0;i<k;i++){
for(int j=i+1;j<k;j++){
if(num[i].x*num[j].y==num[i].y*num[j].x){
num[j].x=1,num[j].y=1;
}
}
}
//排序
sort(num,num+k,cmp);
//输出
cout<<"0/1"<<endl;
for(int i=0;i<k;i++){
if(num[i].x==1&&num[i].y==1) break; //遇见标记直接跳出循环
else cout<<num[i].x<<"/"<<num[i].y<<endl;
}
cout<<"1/1"<<endl;
return 0;
}利用最大公约数模板改进暴力法(AC):
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n;
typedef pair<int,int>pii;
pii num[100005];
int gcd(int a,int b){ //最大公约数
return b?gcd(b,a%b):a;
}
bool cmp(pii a,pii b){
return a.x*b.y<a.y*b.x;
}
int main(){
cin>>n;
int cnt=0;
//若最大公约数为1则存储
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++){
if(gcd(i,j)==1){
num[cnt++]={j,i};
}
}
}
//排序
sort(num,num+cnt,cmp);
//输出
for(int i=0;i<cnt;i++){
cout<<num[i].x<<"/"<<num[i].y<<endl;
}
return 0;
}递归优化(AC);
#include<iostream>
using namespace std;
int n;
void dfs(int a,int b,int c,int d){
if(b+d>n) return ;
dfs(a,b,a+c,b+d);
cout<<a+c<<"/"<<b+d<<endl;
dfs(a+c,b+d,c,d);
}
int main(){
cin>>n;
cout<<"0/1"<<endl;
dfs(0,1,1,1);
cout<<"1/1"<<endl;
return 0;
}AcWing 1225. 正则问题(第八届省赛)
暴力模拟(AC):
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int len, a[100];
int judge(string temp) {
int flag = 0, key = 0;
for (int i = 0; i < temp.size(); i++) {
if (temp[i] == '(') flag = 1;
if (temp[i] == ')') key = 1;
if (flag + key == 2) return 0;
}
return 1;
}
string fun(string str) {
memset(a, 0, sizeof(a));
int l = 0, r = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == ')') {
r = i;
int flag = 0, k = 0;
for (int j = r - 1; j >= 0; j--) {
if(str[j]=='('){
l = j; break;
}
if (str[j] == '|') {
flag = 1;
a[k++] = j;
}
}
if (flag == 0) {
str.erase(r, 1); str.erase(l, 1);
}
else {
a[k++] = l, a[k++] = r;
sort(a, a + k);
for (int i = 0; i < k - 1; i++) {
a[i] = a[i + 1] - a[i] - 1;
}
sort(a, a + k - 1);
str.erase(l, r - l + 1);
string tt = "x";
while (a[k - 2]--) {
str.insert(l, tt);
}
}
return str;
}
}
}
int main() {
ios::sync_with_stdio(false);
string s = ""; cin >> s;
len = s.size();
while (judge(s) == 0)
s = fun(s);
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == ')') {
s.erase(i, 1);
}
}
memset(a, 0, sizeof(a));
int j = 1; a[0] = -1;
int flag = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '|') {
flag = 1;
a[j++] = i;
}
}
a[j] = s.size();
for (int i = 0; i < j; i++)
a[i] = a[i + 1] - a[i] - 1;
sort(a, a + j);
if (flag == 0) cout << s.size() << endl;
else cout << a[j - 1] << endl;
return 0;
}这暴力我自己写出来都不想看......
递归优化(AC):
#include<iostream>
using namespace std;
int n;
string str;
int dfs(){
int res=0;
while(n<str.size()) {
if(str[n]=='(') {
n++;
res+=dfs();
n++;
}
else if(str[n]==')') break;
else if(str[n]=='|') {
n++;
res=max(res,dfs());
}
else {
n++;
res++;
}
}
return res;
}
int main(){
cin>>str ;
cout<<dfs();
return 0 ;
}AcWing 1225. 正则问题类似于洛谷P1928外星密码
P1928 外星密码
暴力模拟(AC):
#include<iostream>
using namespace std;
string str = "";
int len, l, r;
int judge(string a) {
for (int i = 0; i < a.size(); i++)
if (a[i] == '[')
return 0;
return 1;
}
string jieyasuo(string s) {
len = s.size();
for (int i = 0; i < len; i++) {
if (s[i] == ']') {
r = i;
for (int j = r; j >= 0; j--) {
if (s[j] == '[') {
l = j;
int cnt = 0;
int ll = l;
if (s[j + 2] >= '0' && s[j + 2] <= '9') {
cnt = 10 * (s[j + 1] - '0') + (s[j + 2] - '0');
ll += 2;
}
else {
cnt = (s[j + 1] - '0');
ll += 1;
}
string temp = "";
for (int k = ll + 1; k < r; k++)
temp += s[k];
s.erase(l, r - l + 1);
while (cnt--) {
s.insert(l, temp);
}
temp.clear();
return s;
}
}
}
}
}
int main() {
cin >> str;
while (judge(str) != 1)
str = jieyasuo(str);
cout << str << endl;
return 0;
}递归优化:
#include<iostream>
using namespace std;
string dfs(){
string s1="";
char ch;
while(cin>>ch){
if(ch=='['){
int num;
cin>>num;
string s2=dfs();
while(num--) s1+=s2;
}
else if(ch==']')
return s1;
else
s1+=ch;
}
return s1;
}
int main(){
cout<<dfs();
return 0;
}AcWing 1209. 带分数(第四届省赛)
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
pii part[100];
int ans[3],flag[9]={1,2,3,4,5,6,7,8,9};
int cnt,res;
//递归
void dfs(int x,int startt){
if(x>2){
part[cnt].first=ans[1];
part[cnt].second=ans[2];
cnt++;
return ;
}
for(int i=startt;i<=8;i++){
ans[x]=i;
dfs(x+1,i+1);
ans[x]=0;
}
}
//计算区域内的数
int sum(int l,int r){
int t=0;
for(int i=l;i<r;i++) t=t*10+flag[i];
return t;
}
int main(){
//输入
int n;cin>>n;
//给一个区间划分两次,得三份
dfs(1,1);
//遍历每一次全排列
do{
int i=0;
//遍历每一次划分
for(i;i<cnt;i++){
int a=sum(0,part[i].first);
int b=sum(part[i].first,part[i].second);
int c=sum(part[i].second,9);
//判断答案
if(n*c==a*c+b) res++;
}
}while(next_permutation(flag,flag+9));
//输出
cout<<res<<endl;
return 0;
}