Jloi 2015 해 봐.
<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">T1</span>
관찰 식 은 구조 수열 을 통 해 항목 을 추론 할 수 있다
그리고 나머지 는 행렬 곱셈 입 니 다.
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll unsigned long long
#define mod 7528443412579576937ull
using namespace std;
inline void splay(ll &v){
v=0;char c=0;ll p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
ll b,d,n,A,B;
ll mul(ll a,ll b)
{
ll ans=0;a%=mod;
for(ll i=b;i;i>>=1,a=(a+a)%mod)
if(i&1)ans=(ans+a)%mod;
return ans;
}
struct M{
ll a[2][2];
M(){
memset(a,0,sizeof(a));
}
friend M operator * (M a,M b){
M ans;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
(ans.a[i][j]+=mul(a.a[i][k],b.a[k][j]))%=mod;
return ans;
}
friend M operator ^ (M a,ll b){
M ans;
ans.a[0][0]=ans.a[1][1]=1;
for(ll i=b;i;i>>=1,a=a*a)
if(i&1)ans=ans*a;
return ans;
}
}a,ans;
int main()
{
splay(b);splay(d);splay(n);
A=b;B=(d-b*b)/4;
a.a[0][1]=1;a.a[1][0]=B;a.a[1][1]=A;
ans.a[0][0]=2;ans.a[1][0]=b;
ll f=b*b!=d&&n%2==0?1:0;
cout<<(((a^n)*ans).a[0][0]-f+mod)%mod<<endl;
return 0;
}
T2
방법 은 두 가지 가 있다.
첫 번 째 로 왼쪽 에 표 시 를 하고 AHoi 2009 문 제 를 생각해 보 세 요. 먼저 곱 한 다음 에 추가 하고 매번 합병 한 후에 표 시 를 합 니 다.
아래 에서 위로 깊이 에 따라 키워드 로 정렬 합 니 다.
복잡 도 n ^ log n
두 번 째 체인 절개, 선분 수 는 현재 노드 가 뒤로 가 는 곱셈 과 덧셈 을 기록 합 니까? 아니면 AHoi 문 제 를 생각해 보 세 요. 선분 수 는 똑 같 습 니 다.
복잡 도 n * log ^ 2n
나 는 pushdown 이 update 가 되 었 기 때문에 첫 번 째 글 을 썼 다.밤새 틀 릴 까 봐 불필요 한 부분 을 많이 넣 었 기 때문에 상수 가 매우 크다.
몇 살 이 야?어쨌든 n * log ^ 2n 보다 3 배 느 려 요.체득 하 다
참고 로 시 10 초 마다 bzoj 는 모두 10 초 입 니 다.글 쎄, T 야.
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
#define canspd(i) {if(C[i]!=1||J[i]!=0)pushdown(i);}
using namespace std;
inline void splay(ll &v){
v=0;char c=0;ll p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
struct Edge{
ll to,next;
}edge[600010];
ll first[300010],size;
void addedge(ll x,ll y){
size++;
edge[size].to=y;
edge[size].next=first[x];
first[x]=size;
}
#define N 300010
ll root[N];
ll C[N],J[N];
ll ls[N],rs[N];
ll val[N],dis[N];
ll tot,n,m,fang[N];
ll deep[N],fa[N];
ll ans1[N],ans2[N];
ll a[N],v[N],sta[N];
void M(ll c,ll d,ll now){
if(now){
J[now]=c*J[now]+d;
C[now]*=c;
}
}
void pushdown(ll now){
val[now]=val[now]*C[now]+J[now];
M(C[now],J[now],ls[now]),M(C[now],J[now],rs[now]);
C[now]=1,J[now]=0;
}
void update(ll now){
pushdown(now);
if(dis[ls[now]]<dis[rs[now]])swap(ls[now],rs[now]);
dis[now]=dis[rs[now]]+1;
}
void merge(ll a,ll b){
canspd(a);canspd(b);
canspd(ls[a]);canspd(rs[a]);
canspd(ls[b]);canspd(rs[b]);
if(!rs[a]){
rs[a]=b;
update(b),update(a);
return;
}
if(val[b]<val[rs[a]])swap(rs[a],b);
merge(rs[a],b),update(rs[a]),update(ls[a]),update(a);
}
void join(ll a,ll b){//a.join(b)
pushdown(root[a]),pushdown(root[b]);
if(!root[a]){
root[a]=root[b];
root[b]=0;
return;
}
if(!root[b])return;
if(val[root[a]]>val[root[b]]){
merge(root[b],root[a]);
root[a]=root[b];root[b]=0;
}
else{
merge(root[a],root[b]);
root[b]=0;
}
}
void bfs(){
queue<ll>q;
q.push(1);
while(!q.empty()){
ll a=q.front();q.pop();
deep[a]=deep[fa[a]]+1;
for(ll u=first[a];u;u=edge[u].next){
q.push(edge[u].to);
}
}
}
void dfs(ll now){
if(!now)return;
ans2[now]=sta[now];
dfs(ls[now]),dfs(rs[now]);
C[now]=1;J[now]=0;
}
int main(){
int _q=30<<20;
char *_p=(char*)malloc(_q)+_q;
__asm__("movl %0, %%esp
"::"r"(_p));
splay(n),splay(m);
for(ll i=1;i<=n;i++){
splay(fang[i]);
}
for(ll i=2;i<=n;i++){
splay(fa[i]);
splay(a[i]),splay(v[i]);
addedge(fa[i],i);
}
bfs();priority_queue< pair<ll,ll> >que;
for(ll i=1;i<=m;i++){
ll x,y;splay(x),splay(y);
if(x<fang[y]){
ans1[y]++;continue;
}
C[i]=1;sta[i]=deep[y];
val[i]=x,dis[i]=1;root[N-1]=i;
join(y,N-1);
que.push(make_pair(deep[y],y));
}
while(!que.empty()){
ll now=que.top().second;que.pop();
if(!root[now])continue;
pushdown(root[now]),pushdown(ls[root[now]]),pushdown(rs[root[now]]);
while(val[root[now]]<fang[now]&&root[now]){
ans1[now]++,ans2[root[now]]=sta[root[now]]-deep[now];
if(!ls[root[now]]&&rs[root[now]])root[now]=rs[root[now]];
else if(ls[root[now]]&&!rs[root[now]])root[now]=ls[root[now]];
else if(!ls[root[now]]&&!rs[root[now]]){root[now]=0;break;}
else{
if(val[ls[root[now]]]<val[rs[root[now]]])merge(ls[root[now]],rs[root[now]]),root[now]=ls[root[now]];
else merge(rs[root[now]],ls[root[now]]),root[now]=rs[root[now]];
}
pushdown(ls[root[now]]),pushdown(rs[root[now]]);
}
if(!root[now])continue;
if(now!=1){
que.push(make_pair(deep[fa[now]],fa[now]));
pushdown(root[now]);
if(a[now]==1)C[root[now]]=v[now];
else J[root[now]]=v[now];
join(fa[now],now);
}
else{
dfs(root[1]);root[1]=0;
}
}
for(ll i=1;i<=n;i++)printf("%lld
",ans1[i]);
for(ll i=1;i<=m;i++)printf("%lld
",ans2[i]);
}
T3
모든 장 비 를 m 차원 벡터 의 점 으로 보고 cost 에 따라 순 위 를 매 길 때마다 가장 좋 은 것 을 고 르 려 고 합 니 다.
가장 좋 은 것 을 어떻게 판단 합 니까? 우 리 는 cost 에 따라 순 서 를 매 긴 다음 에 고 스 소 원, 이렇게 복잡 도 n ^ 3
현학: eps = 1e - 5 100 pts;eps=1e-6 90pts;eps=1e-8 70pts;eps=1e-18 10pts
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define ul unsigned ll
#define H 23333333ull
#define eps 1e-5
#include<map>
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
int cost[505];
double a[505][505];
int n,m,ans,tot;
int ctr[505];
struct sorted{
int cost,id;
bool operator < (const sorted &b)const{
return cost<b.cost;
}
}s[505];
/*int gcd(int a,int b){
return b=0?a:gcd(b,a%b);
}
ul gethash(int x,int y){
static ul fid[505];
for(int i=1;i<=m;i++){
fid[i]=a[x][i]-a[y][i];
}
if(fid[1]<0){
for(int i=1;i<=m;i++){
fid[i]=-fid[i];
}
}
int g=fid[1];
for(int i=2;i<=m;i++)if(fid[i]!=0)g=gcd(g,abs(fid[i]));
for(int i=1;i<=m;i++)fid[i]/=g;
ul ret=17;
for(int i=1;i<=m;i++)ret=ret*H+(ul)fid[i];
return ret;
}*/
int main(){
splay(n),splay(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;splay(x);
a[i][j]=(double)x;
}
}
for(int i=1;i<=n;i++)splay(cost[i]);
/*for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
dis[i][j]=dis[j][i]=gethash(i,j);
}
}*/
for(int i=1;i<=n;i++){
s[i].id=i;
s[i].cost=cost[i];
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
int v=s[i].id;
for(int j=1;j<=m;j++){
if(fabs(a[v][j])>eps){
if(ctr[j]==0){
ctr[j]=v;
ans++;tot+=cost[v];
break;
}
else{
double x=a[v][j]/a[ctr[j]][j];
for(int k=1;k<=m;k++){
a[v][k]-=x*a[ctr[j]][k];
}
}
}
}
}
cout<<ans<<" "<<tot<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.