首页 > 编程语言 >洛谷【算法1-3】暴力枚举

洛谷【算法1-3】暴力枚举

时间：2024-02-24 12:55:23浏览次数：26  
标签：洛谷 int ll 算法 long 枚举 DFS ans const

P2241 统计方形（数据加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
ll n,m,z,c;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==j) z+=(n-i)*(m-j);
            else c+=(n-i)*(m-j);
        }
    }
    cout<<z<<" "<<c<<" "<<"\n";
    
    return 0;
}

P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,ans=0,a[10000][10],b[10];
void DFS(int tot,int cnt){
    if(cnt==10){
        if(tot==n){
            for(int i=0;i<10;i++) a[ans][i]=b[i];
            ans++;
        }
    }else if(tot>=n) ;
    else{
        for(int i=1;i<=3;i++){
            b[cnt]=i;
            DFS(tot+i,cnt+1);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    DFS(0,0);
    cout<<ans<<"\n";
    for(int i=0;i<ans;i++){
        for(int j=0;j<10;j++) cout<<a[i][j]<<" ";
        cout<<"\n";
    }
    
    return 0;
}

P1008 [NOIP1998 普及组] 三连击 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int num[10]={0};
bool vis[10]={0};
int f(int m){
    int sum=0;
    for(int i=3*m-2;i<=3*m;i++){
        sum*=10;
        sum+=num[i];
    }
    return sum;
}
void DFS(int n){
    if(n==10&&f(1)*2==f(2)*1&&f(1)*3==f(3)*1){
        cout<<f(1)<<" "<<f(2)<<" "<<f(3)<<endl;
        return ;
    }
    for(int i=1;i<=9;i++){
        if(!vis[i]){
            num[n]=i;
            vis[i]=1;
            DFS(n+1);
            vis[i]=0;
        }
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    DFS(1);
    
    return 0;
}

P1618 三连击（升级版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int a,b,c,num[10]={0};
bool vis[10]={0},ans=false;
int f(int m){
    int sum=0;
    for(int i=3*m-2;i<=3*m;i++){
        sum*=10;
        sum+=num[i];
    }
    return sum;
}
void DFS(int n){
    if(n==10&&f(1)*b==f(2)*a&&f(1)*c==f(3)*a){
        cout<<f(1)<<" "<<f(2)<<" "<<f(3)<<endl;
        ans=true;
        return ;
    }
    for(int i=1;i<=9;i++){
        if(!vis[i]){
            num[n]=i;
            vis[i]=1;
            DFS(n+1);
            vis[i]=0;
        }
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>a>>b>>c;
    DFS(1);
    if(!ans) cout<<"No!!!";
    
    return 0;
}

P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,k,a[30],ans=0; 
bool isprime(int x){
    if(x==1) return false;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0) return false;
    }
    return true;
}
void DFS(int last,int sum,int cur){
    if(cur==k){
        if(isprime(sum)) ans++;
        return ;
    }
    for(int i=last;i<=n;i++) DFS(i+1,sum+a[i],cur+1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    DFS(1,0,0);
    cout<<ans<<endl;
    
    return 0;
}

P1157 组合的输出 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,r,a[100];
void DFS(int t){
    if(t>r){
        for(int i=1;i<=r;i++) cout<<setw(3)<<a[i];
        cout<<endl;
        return ;
    }
    for(int i=a[t-1]+1;i<=n;i++){
        a[t]=i;
        DFS(t+1);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>r;
    DFS(1);
    
    return 0;
}

P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,vis[100],a[100];
void DFS(int k){
    if(k==n){
        for(int i=1;i<=n;i++) cout<<setw(5)<<a[i];
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            a[k+1]=i;
            DFS(k+1);
            vis[i]=0;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    DFS(0);
    
    return 0;
}

P1088 [NOIP2004 普及组] 火星人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=1e4+10;
int n,m,a[maxn],cnt,flag;
bool vis[maxn];
void DFS(int step){
    if(flag) return ;
    if(step>n){
        cnt++;
        if(cnt==m+1){
            for(int i=1;i<=n;i++) cout<<a[i]<<" ";
            cout<<"\n";
            flag=true;
        }
        return ;
    }
    for(int i=1;i<=n;i++){
        if(cnt==0) i=a[step];
        if(!vis[i]){
            vis[i]=1;
            a[step]=i;
            DFS(step+1);
            vis[i]=0;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    DFS(1);
    
    return 0;
}

P3392 涂国旗 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,ans=INF,w[60],b[60],r[60];
string s;
int check(char ch){
    int tot=0;
    for(int i=0;i<m;i++) 
        if(s[i]!=ch) ++tot;
    return tot;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s;
        w[i]=w[i-1]+check('W');
        b[i]=b[i-1]+check('B');
        r[i]=r[i-1]+check('R');
    }
    for(int i=1;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            ans=min(ans,w[i]+b[j]-b[i]+r[n]-r[j]);
    cout<<ans<<"\n";
    
    return 0;
}

P3654 First Step (ファーストステップ) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int r,c,k,ans,dir[2][2]={{0,1},{1,0}};
char mp[110][110];
void DFS(int x,int y,int i,int j){
    if(j>k){
        ans++;
        return ;
    }
    if(mp[x][y]!='.' || x<0 || y<0 || x>=r || y>=c) return ;
    DFS(x+dir[i][0],y+dir[i][1],i,j+1);
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>r>>c>>k;
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++) cin>>mp[i][j];
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(mp[i][j]=='.'){
                for(int k=0;k<2;k++) DFS(i,j,k,1);
            }
        }
    }
    if(k==1) ans/=2;
    cout<<ans<<endl;
    
    return 0;
}

P1217 [USACO1.5] 回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
bool ispalindrome(int x);
bool isprime(int x);
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(ispalindrome(i)&&isprime(i)){
            cout<<i<<endl;
        }
    }
    return 0;
}
bool ispalindrome(int x){
    int c[10],count=0;
    while(x!=0){
        c[count++]=x%10;
        x/=10;
    }
    for(int i=0;i<count;i++,count--){
        if(c[count-1]!=c[i]){
            return false;
        }
    }
    return true;
}
bool isprime(int x){
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}

P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
//0 1 2 3 4 5 6 7 8 9
//6 2 5 5 4 5 6 3 7 6
int n,ans=0,x[1001]={6,2,5,5,4,5,6,3,7,6},b[4];
void DFS(int t){
    for(int i=0;i<=999;i++){
        if(n-x[i]>=0){
            b[t]=i;
            n-=x[i];
            if(t==3){
                if(b[1]+b[2]==b[3] && n==0) ans++;
            }else DFS(t+1);
            n+=x[i];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    n-=4;
    for(int i=10;i<=999;i++) x[i]=x[i/10]+x[i%10];
    DFS(1);
    cout<<ans<<"\n";
    return 0;
}

P3799 妖梦拼木棒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
ll n,ans,maxa,a[N],num[N];
ll C(ll x,ll k){
    return (k==1ll?x:x*(x-1ll)/2ll)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxa=max(maxa,a[i]);
        num[a[i]]++;
    }
    for(int i=2;i<=maxa;i++){
        if(num[i]>=2ll){
            ll t=C(num[i],2ll)%mod;
            for(int j=1;j<=i/2;j++){
                if(j!=i-j&&num[j]>=1&&num[i-j]>=1){
                    ans+=t*C(num[j],1)*C(num[i-j],1)%mod;
                }
                if(j==i-j&&num[j]>=2){
                    ans+=t*C(num[j],2)%mod;
                }
                ans%=mod;
            }
        }
    }
    cout<<ans<<"\n";
        
    return 0;
}

P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int s[5],a[5][20],ans,res=0,l,r;
void DFS(int sub,int pos){
    if(pos>s[sub]){
        ans=min(ans,max(l,r));
        return ;
    }
    l+=a[sub][pos];
    DFS(sub,pos+1);
    l-=a[sub][pos];
    r+=a[sub][pos];
    DFS(sub,pos+1);
    r-=a[sub][pos];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>s[1]>>s[2]>>s[3]>>s[4];
    for(int i=1;i<=4;i++){
        ans=INF;
        l=0,r=0;
        for(int j=1;j<=s[i];j++) cin>>a[i][j];
        DFS(i,1);
        res+=ans;
    }
    cout<<res<<endl;
    
    return 0;
}

P2036 [COCI2008-2009 #2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,s[15],b[15],vis[15],ss=1,bb=0,ans=INF;
void DFS(int cnt){
    if(cnt>n) return ;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            ss*=s[i];
            bb+=b[i];
            ans=min(ans,abs(ss-bb));
            vis[i]=1;
            DFS(cnt+1);
            vis[i]=0;
            ss/=s[i];
            bb-=b[i];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i]>>b[i];
    DFS(1);
    cout<<ans<<endl;
    
    return 0;
}

 

标签：洛谷,int,ll,算法,long,枚举,DFS,ans,const
From： https://www.cnblogs.com/accbulb/p/18030961

相关文章

  • 代码随想录算法训练营第二十七天 | 90.子集II ， 78.子集， 93.复原IP地址
    93.复原IP地址 已解答中等 相关标签相关企业 有效IP地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP地址，但是 "0.011.255.245"、"1......
  • 算法-字符串
    1.反转字符串(LeetCode344)题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。思路：双指针，左边和右边对应位置的依次交换classSolution{......
  • KMP 字符串搜索算法
    KMP字符串搜索算法是Knuth、Morris、Pratt三位在类似的时间段内一起发明的一种字符串搜索算法，该算法的主要原理是利用待查找子串中的某些信息，在匹配失败时能够减少回退的步数算法原理假设现在有一个待搜索的字符串ABABAC，如何利用现有的字符串实现在字符不匹配时尽可能向后调......
  • 代码随想录算法训练营day03 | leetcode 203. 移除链表元素、707. 设计链表、206. 反转
    目录题目链接：203.移除链表元素-简单题目链接：707.设计链表-中等题目链接：206.反转链表-简单题目链接：203.移除链表元素-简单题目描述：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val==val的节点，并返回新的头节点。示例1：输入：head=[1,2,6......
  • 2024牛客寒假算法基础集训营6
    2024牛客寒假算法基础集训营6比赛链接打一半就收拾行李了，不想开学呜呜呜(应该是lzgg出的题)A.宇宙的终结思路数据不大才100，所以模拟完全可以过去Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineall(x)x.begin()+1,x.end()std::vector<......
  • 代码随想录算法训练营第二十六天| 39. 组合总和 40.组合总和II 131.分割回文串
    组合总和题目链接：39.组合总和-力扣（LeetCode）思路：依然一是套用回溯模板，但是我们这里用回溯的是i而不是i+1，因为元素可以重复使用，注意for循环里if(sum(path)<=target)的等号不能少。classSolution{public:vector<int>path;vector<vector<int>>result;intsu......
  • 2024牛客寒假算法基础集训营6
    A.宇宙的终结Code(伪代码):voidsolve(){intleft,right;cin>>left>>right;autocheck1=[&](intn){for(inti=2;i<=sqrt(n);i++){if(n%i==0){returnfalse;}......
  • 排序算法汇总：希尔、快速、堆、归并
    排序思想分类比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。（大部分排序算法）非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序（计数......
  • KMP字符串匹配算法
    什么是KMPKMP算法主要应用在字符串匹配问题。因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP 核心思想KMP的主要思想是：「当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。」（可......
  • 递归与回溯算法
    递归函数中自己调用自己经典例题：汉诺塔需要将所有盘子按顺序放到塔C上（问题规模：n）就需要最大的盘子在C底部就需要将其余所有盘子移动到塔B上 第二塔上也需要按顺序摆放（问题规模：n-1）就需要第二大的盘子在B底部就需要将其余所有盘子移动到另一个塔上··········......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99