asdypeij

42

hepanrong.

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define int long long
const int maxn=5005;

#define x1 dxfgbhj
#define x2 rctvybjn
#define y1 rtgbhn
#define y2 hughmjn

int n,m,x1,y1,x2,y2,u,l,x,y;

struct Point{
int x,y;
Point(){}
Point(int _x,int _y){x=_x,y=_y;}
Point operator -(const Point p)const{
return Point(x-p.x,y-p.y);
}
void print(){
cerr<<"("<<x<<","<<y<<") ";
}
}p[maxn][2],toy[maxn];

int tot[maxn];

int cross(Point a,Point b){
return a.x*b.y-b.x*a.y;
}

bool check(int i){
Point v1=p[i][1]-p[i][0],v2=Point(x,y)-p[i][0];
return cross(v2,v1)>0;
}

signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int i=0;

while(cin>>n>>m>>x1>>y1>>x2>>y2&&n){
if(i) cout<<endl;
memset(tot,0,sizeof tot);
F(i,1,n){
cin>>u>>l;
p[i][0]={u,y1},p[i][1]={l,y2};
}
p[n+1][0]={x2,y1},p[n+1][1]={x2,y2};
// F(i,1,n+1) p[i][0].print(),p[i][1].print(),cerr<<endl;
F(i,1,m){
cin>>x>>y;
int l=1,r=n+1;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
tot[l-1]++;
}
F(i,0,n) cout<<i<<": "<<tot[i]<<endl;
i++;
}
return 0;
}



asdypeij
23天前
#include<bits/stdc++.h>
#define F(i,j,k) for(signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
using namespace std;
const int maxn=1e5+5;

int n,m,ans[maxn];

struct Fentree{
int t[maxn*2];
int query(int x){
int ans=0;
for(;x;x-=x&-x) ans+=t[x];
return ans;
}
}t;

struct Point{
int a,b,c,cnt=1,ans=0;
bool operator <(const Point& p)const{
if(a!=p.a) return a<p.a;
if(b!=p.b) return b<p.b;
return c<p.c;
}
bool operator ==(const Point& p)const{
return a==p.a&&b==p.b&&c==p.c;
}
}a[maxn],tmp[maxn];

void cdq(int l,int r){
if(l>=r) return;
int mid=(l+r)/2;
cdq(l,mid),cdq(mid+1,r);
int i=l,j=mid+1,k=1;
while(i<=mid&&j<=r){
else a[j].ans+=t.query(a[j].c),tmp[k++]=a[j++];
}
while(j<=r) a[j].ans+=t.query(a[j].c),tmp[k++]=a[j++];
for(int i=l,j=1;i<=r;i++,j++) a[i]=tmp[j];
}

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
F(i,1,n) cin>>a[i].a>>a[i].b>>a[i].c;
sort(a+1,a+1+n);
int k=2;
F(i,2,n) {
if(a[i]==a[k-1]) a[k-1].cnt++;
else a[k++]=a[i];
}
cdq(1,k-1);
F(i,1,k-1) ans[a[i].ans+a[i].cnt-1]+=a[i].cnt;
F(i,0,n-1) cout<<ans[i]<<endl;
return 0;
}



asdypeij
3个月前
// Problem: P1313 [NOIP2011 提高组] 计算系数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1313
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define int long long
const int mod=10007;

int a,b,k,n,m;
int qPow(int a,int b){
int ans=1;
while(b){
if(b%2) (ans*=a)%=mod;
(a*=a)%=mod,b/=2;
}
return ans;
}
int inv(int x){return qPow(x,mod-2);}
int P(int a,int b){//从b个数中选a个数的个数
int ans=1;
for(int i=b,j=1;j<=a;i--,j++) (ans*=i)%=mod;
return ans;
}
int fac(int x){return x==1?1:x*fac(x-1)%mod;}

signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>a>>b>>k>>n>>m;
cout<<qPow(a,n)*qPow(b,m)%mod*P(n,k)%mod*inv(fac(n))%mod<<endl;
return 0;
}



asdypeij
3个月前
// Problem: P8306 【模板】字典树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8306
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
//#define int long long
int T;
struct trie{
struct trie_node{
int cnt=0;
unordered_map<char,int> c;
};
vector<trie_node> a={{}};
void insert(string s){
int node=0;
for(auto i:s) {
if(a[node].c.count(i)) node=a[node].c[i];
else a.push_back({}),a[node].c[i]=a.size()-1,
node=a.size()-1;
}
a[node].cnt++;
}
int get_node(string s){
int node=0,ans=0;
for(auto i:s){
if(a[node].c.count(i)) node=a[node].c[i],ans+=a[node].cnt;
else return ans;
}
return ans;
}
};
string rev(string s){
reverse(begin(s),end(s));
return s;
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
string s;
trie t;
cin>>n>>q;
F(i,1,n) cin>>s,t.insert(s);
F(i,1,q) cin>>s,cout<<t.get_node(s)<<endl;
return 0;
}


asdypeij
3个月前

算法

时间复杂度

$O(1)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,p;
cin>>a>>b>>p;
cout<<(long long)(__int128(a)*b%p);
return 0;
}