不同正整数的个数

思路:每次统计一下,数$x$是否出现过即可.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
map<int,bool>mp;
void solve()
{
       int n;cin>>n;
       vector<int>a(n+1);
       int ans=0;
       for(int i=1;i<=n;i++)
       {
               int x;cin>>x;
               if(!mp[x]&&x>0)ans++,mp[x]=true;
       }
       cout<<ans<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}

最短路径

BFS/思维

思路：
按照图示将图建出来,跑一遍bfs确定一下每个可达点的最短路.
最后确认一下,终点的最短路,是否和操作数一致.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int g[1110][1110];
bool vis[1101][1110];
int dist[1110][1110];
void bfs()
{
        queue<PII>q;
        vis[110][110]=true;
        dist[110][110]=0;
        q.push({110,110});
        while(!q.empty())
        {
                auto t=q.front();
                q.pop();
                for(int i=0;i<4;i++)
                {
                        int nx=dx[i]+t.first;
                        int ny=dy[i]+t.second;
                   //     cout<<nx<<' '<<ny<<endl;
                        if(g[nx][ny]&&!vis[nx][ny])
                        {
                                dist[nx][ny]=dist[t.first][t.second]+1;
                                vis[nx][ny]=true;
                                q.push({nx,ny});
                            //    cout<<nx<<' '<<ny<<endl;
                        }
                }
        }//确定最短路 
        return ;
}
void solve()
{
       string s;cin>>s;
       int x=110,y=110;
       g[1][1]=1;
       for(auto c:s)
       {
                if(c=='U')y++;
                else if(c=='D')y--;
                else if(c=='L')x--;
                else x++;  
                g[x][y]=1;
       }
       bfs();
       if(s.size()!=dist[x][y])cout<<"NO"<<endl;
       else cout<<"YES"<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    //    freopen("test.in","r",stdin);
        solve();
        return 0;
}

合适数对

分解质因数/组合计数/同余类

思路:将每一个数,分解质因数后,每一个质数要满足,乘上另一个数后,对应质因数.能整除$K$
因此,将原数,分解质因数后,每一个质因数对$k$的同余类建立一个线性容器.
然后 每次 检索每一个质因数,对应同余类组合在一起,可以构成多少种即可.从小到大计数,去重.

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<PII>st[N];
map<vector<PII>,int>mp;
void solve()
{
       int n,m;
       cin>>n>>m;
       vector<int>a(n+1);
       for(int i=1;i<=n;i++)cin>>a[i];
       for(int i=1;i<=n;i++)
       {
               for(int k=2;k<=a[i]/k;k++)
               {
                       int s=0;
                       while(a[i]%k==0)a[i]/=k,s++;
                       s%=m;
                       if(s!=0)st[i].push_back({k,s});//st中存的是同余类. 
               }
               if(a[i]!=1)st[i].push_back({a[i],1});
       }//构建所有数 分解质因数 后底数和指数
       ll ans=0; 
       for(int i=1;i<=n;i++)
       {
           vector<PII>tmp;
           for(auto c:st[i])tmp.push_back({c.first,m-c.second});      
           ans+=mp[tmp];
           ++mp[st[i]];//从小到大计数 便于去重 同时存放的是同余类,保证不重不漏 
       } 
       cout<<ans<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        //freopen("test.in","r",stdin);
        solve();
        return 0;
}