长春哪里有做网站的武汉百度seo排名

十年代码一场空，不开long long见祖宗啊，最后一题卡了半个小时，最后索性把int都改成longlong就过了，唉~~

4317. 不同正整数的个数 - AcWing

签到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,res;
map<int,bool> mp;
int main()
{cin>>n;while(n--){int t;cin>>t;if(t<=0) continue;if(!mp[t]) res++;mp[t]=true;}cout<<res;
}

4318. 最短路径 - AcWing 

        根据题意，为了尽可能让这条路线是最短的，将路线上的点设为安全点，其余为陷阱即可。然后BFS求一下起点到终点的最短路和路线长度对比即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<PII,int> PI;
string s;
const int N=505;
bool vis[N][N];
int g[N][N];
PII ed;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int solve()
{queue<PI> q;q.push({{250,250},0});while(!q.empty()){PI t=q.front();q.pop();PII tt=t.first;int d=t.second;int x=tt.first,y=tt.second;if(x==ed.first&&y==ed.second) return d;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(!g[nx][ny]||vis[nx][ny]) continue;vis[nx][ny]=true;q.push({{nx,ny},d+1});}	}
}
int main()
{cin>>s;int x,y;x=y=250;g[x][y]=1;for(int i=0;i<s.length();i++){if(s[i]=='U') x--;else if(s[i]=='D') x++;else if(s[i]=='L') y--;else y++;g[x][y]=1;}ed={x,y};int d=solve();if(d!=s.length()) cout<<"NO";else cout<<"YES";
}

4319. 合适数对 - AcWing 

        由题意我们可以知道，a1*a2=x^k 等价于 a1*a2是可以正好被开k次幂。我们将一个数分解质因数，表示为a=p1^a1*p2^a2`````那么显然上述条件就等价于两数的质因数相乘，每一项的幂数都是k的倍数。由此我们知道，对于一个数，可以通过质因数互补匹配的思路来寻找与其对应（相乘开k次方为整数）的数。由于规定l<r，我们在线处理即可。

        注意对于本身就可以开k次方为整数的数，需要特殊处理出来，其组合个数为n*(n+1)/2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
map<vector<PII>,ll>mp;
int n,k;
ll res;
ll sss;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){int t;cin>>t;vector<PII> vc;for(ll j=2;j*j<=t;j++)if(t%j==0){ll s=0;while(t%j==0){s++;t/=j;}s%=k;if(s) vc.push_back({j,s});}if(t!=1) vc.push_back({t,1});sort(vc.begin(),vc.end());if(!vc.size()){sss++;continue;}vector<PII> nd;for(int i=0;i<vc.size();i++){ll p=vc[i].first,s=vc[i].second;ll nk=k-s;nd.push_back({p,nk});}	res+=mp[nd];mp[vc]++;}res+=sss*(sss-1)/2; cout<<res;
}