Round #2

題源：來自hzwer整理的題

2014-5-10 NOIP模擬賽

by coolyangzc

Problem 1 機器人(robot.cpp/c/pas)

【題目描述】

早苗入手了最新的Gundam模型。最新款自然有著與以往不同的功能，那就是它能夠自動行走，厲害吧。

早苗的新模型可以按照輸入的命令進行移動，命令包括‘E’、‘S’、‘W’、‘N’四種，分別對應東南西北。執行某個命令時，它會向對應方向移動一個單位。作為新型機器人，它可以執行命令串。對于輸入的命令串，每一秒它會按命令行動一次。執行完命令串的最后一個命令后，會自動從頭開始循環。在0時刻時機器人位于（0,0）。求T秒后機器人所在位置坐標。

【輸入格式】

第1行：一個字符串，表示早苗輸入的命令串，保證至少有1個命令

第2行：一個正整數T

【輸出格式】

2個整數，表示T秒時，機器人的坐標。

【樣例輸入】

NSWWNSNEEWN

12

【樣例輸出】

-1 3

【數據范圍】

對于60%的數據 T<=500,000 且命令串長度<=5,000

對于100%的數據 T<=2,000,000,000 且命令串長度<=5,000

【注意】

向東移動，坐標改變改變為(X+1,Y);

向南移動，坐標改變改變為(X,Y-1);

向西移動，坐標改變改變為(X-1,Y);

向北移動，坐標改變改變為(X,Y+1);

簡單模擬題，按照題意從原點(0,0)開始跑一遍命令串cmd，得出cmd[i]時相對于原點的位置，先T-=1再令x=T/|cmd|,y=T%|cmd|，得出機器人沿著命令串cmd跑了x輪，當前停留在命令串y的位置，即可算出答案x*cmd[|cmd|-1]+cmd[y]；

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<utility>
#include<numeric>
#include<iterator>
#include<algorithm>
#include<functional>
#include<ctime>
#include<cassert>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
#define FOR(i,init,len) for(int i=(init);i<(len);++i)
#define For(i,init,len) for(int i=(init);i<=(len);++i)
#define fi first
#define se second
#define pb push_back
#define is insert
namespace IO {
    inline char getchar() {
        static const int BUFSIZE=5201314;
        static char buf[BUFSIZE],*begin,*end;
        if(begin==end) {
            begin=buf;
            end=buf+fread(buf,1,BUFSIZE,stdin);
            if(begin==end) return -1;
        }
        return *begin++;
    }
}
inline void read(int &in) {
    int c,symbol=1;
    while(isspace(c=IO::getchar()));
    if(c=='-') { in=0;symbol=-1; }
    else in=c-'0';
    while(isdigit(c=IO::getchar())) { in*=10;in+=c-'0'; }
    in*=symbol;
}
inline int read() { static int x;read(x);return x; }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
#define PA(name,init,len) cout<<#name"["<<(len-init)<<"]=";FOR(_,init,len) cout<<name[_]<<" \n"[_==(len-1)];
#define Pa(name,init,len) cout<<#name"["<<(len-init+1)<<"]=";For(_,init,len) cout<<name[_]<<" \n"[_==(len)];
#define PV(name) cout<<#name"="<<name<<'\n';

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int c[255];
std::vector<P> v;
std::string s;
int T;

int main() {
#ifdef MengLan
    int Beginning=clock();
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif // MengLan

    cin>>s>>T;
    P now(0,0);
    c['E']=0;c['N']=1;c['W']=2;c['S']=3;
    for(auto ch:s){
        int dir=c[ch];
        now=P(now.fi+dx[dir],now.se+dy[dir]);
        v.pb(now);
    }
    --T;
    int x=T/s.size(),y=T%s.size();
    //PV(x)PV(y)
    printf("%d %d\n",v.back().fi*x+v[y].fi,v.back().se*x+v[y].se);

#ifdef MengLan
    printf("Time: %d\n",clock()-Beginning);
    system("pause");
#endif // MengLan
    return 0;
}

View Code

Problem 2 數列(seq.cpp/c/pas)

【題目描述】

a[1]=a[2]=a[3]=1

a[x]=a[x-3]+a[x-1] (x>3)

求a數列的第n項對1000000007（10^9+7）取余的值。

【輸入格式】

第一行一個整數T，表示詢問個數。

以下T行，每行一個正整數n。

【輸出格式】

每行輸出一個非負整數表示答案。

【樣例輸入】

3

6

8

10

【樣例輸出】

4

9

19

【數據范圍】

對于30%的數據 n<=100；

對于60%的數據 n<=2*10^7；

對于100%的數據 T<=100，n<=2*10^9；

眾所周知，求fib(斐波那契數列)第n項f[n]%mod可以通過矩陣快速冪求得，而且本題和fib一樣都屬于線性遞推，那么只需要構造一個矩陣A，使得

f(x)		a1	b1	c1		f(x-1)
f(x-1)	=	a2	b2	c2	*	f(x-2)
f(x-2)		a3	b3	c3		f(x-3)

則可以通過矩陣左乘一次A，從f(x)推出下一項f(x+1)，已知前三項均為1，則可以通過左乘A^(n-3)推出f(n)；

那么依據矩陣乘法：

f(x)=a1*f(x-1)+b1*f(x-2)+c1*f(x-3)

f(x-1)=a2*f(x-1)+b2*f(x-2)+c2*f(x-3)

f(x-2)=a3*f(x-1)+b3*f(x-2)+c3*f(x-3)

由于本題f(x)=f(x-1)+f(x-3)

那么顯然系數為：

a1=1,b1=0,c1=1；

a2=1,b2=0,c2=0;

a3=0,b3=1,c3=0;

那么直接通過矩陣快速冪算得A^(n-3)即可解決；

由于本人比較懶，代碼直接使用3*3矩陣進行運算；

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<utility>
#include<numeric>
#include<iterator>
#include<algorithm>
#include<functional>
#include<ctime>
#include<cassert>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
#define FOR(i,init,len) for(int i=(init);i<(len);++i)
#define For(i,init,len) for(int i=(init);i<=(len);++i)
#define fi first
#define se second
#define pb push_back
#define is insert
namespace IO {
    inline char getchar() {
        static const int BUFSIZE=5201314;
        static char buf[BUFSIZE],*begin,*end;
        if(begin==end) {
            begin=buf;
            end=buf+fread(buf,1,BUFSIZE,stdin);
            if(begin==end) return -1;
        }
        return *begin++;
    }
}
inline void read(int &in) {
    int c,symbol=1;
    while(isspace(c=IO::getchar()));
    if(c=='-') { in=0;symbol=-1; }
    else in=c-'0';
    while(isdigit(c=IO::getchar())) { in*=10;in+=c-'0'; }
    in*=symbol;
}
inline int read() { static int x;read(x);return x; }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
#define PA(name,init,len) cout<<#name"["<<(len-init)<<"]=";FOR(_,init,len) cout<<name[_]<<" \n"[_==(len-1)];
#define Pa(name,init,len) cout<<#name"["<<(len-init+1)<<"]=";For(_,init,len) cout<<name[_]<<" \n"[_==(len)];
#define PV(name) cout<<#name"="<<name<<'\n';

const ll mod =1e9+7;
struct Matrix{
    ll d[3][3];
    Matrix(){memset(d,0,sizeof(d));}
    Matrix operator*(const Matrix &rhs)const{
        Matrix ret;
        for(int i=0;i<3;++i) for(int j=0;j<3;++j) {for(int k=0;k<3;++k) ret.d[i][j]+=d[i][k]*rhs.d[k][j]%mod;ret.d[i][j]%=mod;}
        return ret;
    }
    Matrix operator+(const Matrix &rhs)const{
        Matrix ret;
        FOR(i,0,3) FOR(j,0,3){
            ret.d[i][j]=d[i][j]+rhs.d[i][j];
            if(ret.d[i][j]>mod) ret.d[i][j]-=mod;
        }
        return ret;
    }
    void print(){
        FOR(i,0,3) FOR(j,0,3) printf("%lld%c",d[i][j],j==2?'\n':' ');
    }
};

Matrix qpow(int n){
    Matrix a,ret;
    a.d[0][0]=a.d[0][2]=a.d[1][0]=a.d[2][1]=1;
    ret.d[0][0]=ret.d[1][0]=ret.d[2][0]=1;
    while(n){
        if(n&1) ret=a*ret;
        n>>=1;
        a=a*a;
    }
    return ret;
}

int main() {
#ifdef MengLan
    int Beginning=clock();
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif // MengLan

    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        if(n<=3) puts("1");
        else{
            auto ans=qpow(n-3);
            printf("%lld\n",(ans.d[0][0]%mod+mod)%mod);
        }
    }

#ifdef MengLan
    printf("Time: %d\n",clock()-Beginning);
    system("pause");
#endif // MengLan
    return 0;
}

View Code

Problem 3 蟲洞(holes.cpp/c/pas)

【題目描述】

N個蟲洞，M條單向躍遷路徑。從一個蟲洞沿躍遷路徑到另一個蟲洞需要消耗一定量的燃料和1單位時間。蟲洞有白洞和黑洞之分。設一條躍遷路徑兩端的蟲洞質量差為delta。

1.從白洞躍遷到黑洞，消耗的燃料值減少delta，若該條路徑消耗的燃料值變為負數的話，取為0。

2.從黑洞躍遷到白洞，消耗的燃料值增加delta。

3.路徑兩端均為黑洞或白洞，消耗的燃料值不變化。

作為壓軸題，自然不會是如此簡單的最短路問題，所以每過1單位時間黑洞變為白洞，白洞變為黑洞。在飛行過程中，可以選擇在一個蟲洞停留1個單位時間，如果當前為白洞，則不消耗燃料，否則消耗s[i]的燃料。現在請你求出從蟲洞1到N最少的燃料消耗，保證一定存在1到N的路線。

【輸入格式】

第1行：2個正整數N,M

第2行：N個整數，第i個為0表示蟲洞i開始時為白洞，1表示黑洞。

第3行：N個整數，第i個數表示蟲洞i的質量w[i]。

第4行：N個整數，第i個數表示在蟲洞i停留消耗的燃料s[i]。

第5..M+4行：每行3個整數，u,v,k，表示在沒有影響的情況下，從蟲洞u到蟲洞v需要消耗燃料k。

【輸出格式】

一個整數，表示最少的燃料消耗。

【樣例輸入】

4 5

1 0 1 0

10 10 100 10

5 20 15 10

1 2 30

2 3 40

1 3 20

1 4 200

3 4 200

【樣例輸出】

130

【數據范圍】

對于30%的數據： 1<=N<=100,1<=M<=500

對于60%的數據： 1<=N<=1000,1<=M<=5000

對于100%的數據： 1<=N<=5000，1<=M<=30000

其中20%的數據為1<=N<=3000的鏈

1<=u,v<=N, 1<=k,w[i],s[i]<=200

【樣例說明】

按照1->3->4的路線。

既然題目都說了這是一道最短路問題，那么這就是一道最短路問題了（霧），再加上邊權值>=0，那么理論上用dijkstra的優先度是比SPFA高的；

那么問題只在于怎么建邊了；

首先，蟲洞分黑洞白洞，并且在這兩種狀態中轉換，那么如何去區分黑洞白洞呢？

拆點吧，把一個蟲洞在黑洞和白洞的時候分別用一個點表示，本人習慣用i和i+n，還有一種常見的是i*2和i*2+1，可以使用位運算i<<1和i<<1|1表示；

以下使用點i和i+n表示同一個蟲洞的兩種狀態；

題目有個要求，每隔1單位時間，蟲洞將從黑洞變成白洞或從白洞變成黑洞；

那么對于兩種操作：

1.從任意一個蟲洞到另一個蟲洞，需要1單位時間，假設A是白洞，B是黑洞，從A->B，則抵達時B應該為白洞狀態，那么假設i是A白洞狀態的點，i+n是A黑洞狀態時的點，j是B黑洞狀態時的點，j+n是B白洞狀態時的點，那么將建邊i->j+n，費用為C1和i+n->j，費用為C2；

2.可以在一個蟲洞停留1單位時間，那么就是在蟲洞在黑洞和白洞狀態各向對方連一條單向邊，假設蟲洞的兩個點分別為i和i+n，那么將建邊i->i+n，費用為C1,i+n->i，費用為C2；

以上費用C按題意要求計算；

對于i和i+n與黑洞和白洞對應的方式有兩種，

第一種將i與題目輸入的白洞黑洞對應，那么i+n就為另一種，這樣的好處是對于題目輸入的邊u->v，建邊肯定是u->v+n和u+n->v，關鍵在于費用C的計算；

第二種將i直接與白洞對應，i+n直接與黑洞對應，那么這樣需要判斷輸入的邊u->v中u,v的狀態是否相同，好處是相同的話，費用肯定都是k，不相同的話，一個費用是k-Δ，另一個是k+Δ；

本題貼兩份代碼，第一份是我的，拆點方式為i和i+n，對應方式為按輸入對應(第一種)，最短路用dijkstra

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<utility>
#include<numeric>
#include<iterator>
#include<algorithm>
#include<functional>
#include<ctime>
#include<cassert>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
#define FOR(i,init,len) for(int i=(init);i<(len);++i)
#define For(i,init,len) for(int i=(init);i<=(len);++i)
#define fi first
#define se second
#define pb push_back
#define is insert
namespace IO {
    inline char getchar() {
        static const int BUFSIZE=5201314;
        static char buf[BUFSIZE],*begin,*end;
        if(begin==end) {
            begin=buf;
            end=buf+fread(buf,1,BUFSIZE,stdin);
            if(begin==end) return -1;
        }
        return *begin++;
    }
}
inline void read(int &in) {
    int c,symbol=1;
    while(isspace(c=IO::getchar()));
    if(c=='-') { in=0;symbol=-1; }
    else in=c-'0';
    while(isdigit(c=IO::getchar())) { in*=10;in+=c-'0'; }
    in*=symbol;
}
inline int read() { static int x;read(x);return x; }
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
#define PA(name,init,len) cout<<#name"["<<(len-init)<<"]=";FOR(_,init,len) cout<<name[_]<<" \n"[_==(len-1)];
#define Pa(name,init,len) cout<<#name"["<<(len-init+1)<<"]=";For(_,init,len) cout<<name[_]<<" \n"[_==(len)];
#define PV(name) cout<<#name"="<<name<<'\n';

struct Edge{
    int to,cost;
    Edge(int to=0,int cost=0):to(to),cost(cost){}
};
const int maxn=6e4+10;
std::vector<Edge> G[maxn];
int n,m;
int col[maxn],w[maxn],s[maxn];

struct Lan{
    int u,cost;
    Lan(int u=0,int cost=0):u(u),cost(cost){}
    bool operator<(const Lan &rhs)const{return cost>rhs.cost;}
};

const int INF=1e9;
bool vis[maxn];
int d[maxn];
int dijkstra(){
    std::priority_queue<Lan> q;
    q.push(Lan(1,0));
    For(i,1,n+n) d[i]=INF;d[1]=0;
    while(!q.empty()){
        auto x=q.top();q.pop();
        //printf("u:%d cost:%d\n",x.u,x.cost);
        if(x.u==n||x.u==n+n) return x.cost;
        if(vis[x.u]) continue;
        vis[x.u]=true;
        for(auto &y:G[x.u]) if(d[y.to]>d[x.u]+y.cost){
            d[y.to]=d[x.u]+y.cost;
            q.push(Lan(y.to,d[y.to]));
        }
    }
    return -1;
}

int main() {
#ifdef MengLan
    int Beginning=clock();
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif // MengLan

    scanf("%d%d",&n,&m);
    For(i,1,n) scanf("%d",col+i),col[i+n]=!col[i];
    For(i,1,n) scanf("%d",w+i),w[i+n]=w[i];
    For(i,1,n) scanf("%d",s+i);
    For(i,1,n) {
        if(col[i]) G[i].pb(Edge(i+n,s[i])),G[i+n].pb(Edge(i,0));
        else G[i].pb(Edge(i+n,0)),G[i+n].pb(Edge(i,s[i]));
    }
    For(i,1,m){
        int u,v,k;scanf("%d%d%d",&u,&v,&k);
        int k1=k,k2=k;
        if(!col[u]&&col[v]) k1=k-std::abs(w[u]-w[v]),k2=k+std::abs(w[u]-w[v]);
        if(col[u]&&!col[v]) k1=k+std::abs(w[u]-w[v]),k2=k-std::abs(w[u]-w[v]);
        if(k1<0) k1=0;
        if(k2<0) k2=0;
        G[u].pb(Edge(v+n,k1));
        G[u+n].pb(Edge(v,k2));
    }
    //For(i,1,n+n) for(auto &y:G[i]) printf("u:%d v:%d c:%d\n",i,y.to,y.cost);
    printf("%d\n",dijkstra());

#ifdef MengLan
    printf("Time: %d\n",clock()-Beginning);
    system("pause");
#endif // MengLan
    return 0;
}

View Code

第二份代碼為標程，拆點方式為i*2-1和i*2，對應方式為第二種，最短路算法用SPFA

#include<cstdio>
#include<cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
#define abs(x) (x > 0 ? x : -(x))
const int maxn=10010,maxm=70010,maxq=16383;
int n,m,u,v,k,sz,l,r,x,delta,
    p[maxn],w[maxn],d[maxn],q[maxq+1],en[maxn],pre[maxm],g[maxm],len[maxm];
bool Inq[maxn];
inline void Ins(int u,int v,int d)
{
    pre[++sz]=en[u];en[u]=sz;g[sz]=v;len[sz]=d;
}
void Init_And_Set_Map()
{
       scanf("%d%d",&n,&m);
    rep(i,n) scanf("%d",&p[i]);
    rep(i,n) scanf("%d",&w[i]);
    rep(i,n)
    {
        scanf("%d",&k);
        Ins(i+i-1,i+i,0);
        Ins(i+i,i+i-1,k);
    }
    rep(i,m)
    {
        scanf("%d%d%d",&u,&v,&k);
        if (p[u]==p[v])
        {
            Ins(u+u-1,v+v,k);
            Ins(u+u,v+v-1,k);
        }
        else
        {
            delta=abs(w[u]-w[v]);
            Ins(u+u-1,v+v-1, (k-delta>0 ? k-delta : 0));
            Ins(u+u,v+v, k+delta);
        }
    }
    
}
void SPFA()
{
    memset(d,0x7F,sizeof(d));
    q[0]=p[1]+1;d[q[0]]=l=r=0;
    while ((r+1&maxq) != l)
    {
        x=q[l];l=(l+1)&maxq;Inq[x]=0;
        for(int i=en[x];i;i=pre[i])
        {
            v=g[i];
            if (d[x]+len[i]<d[v])
            {
                d[v]=d[x]+len[i];
                if (Inq[v]) continue;
                Inq[v]=1;
                if (d[v]<d[q[l]]) q[l=(l-1)&maxq]=v;
                             else q[r=(r+1)&maxq]=v;
            }
        }
    }
    
}
int main()
{
    freopen("holes.in","r",stdin);
    freopen("holes.out","w",stdout);
    Init_And_Set_Map();
    SPFA();
    printf("%d",d[n+n-1]<d[n+n] ? d[n+n-1] : d[n+n]);
    return 0;
}

View Code

posted @ 2018-05-10 21:00 漫無目的的尋閱讀(185) 評論(0) 收藏舉報

刷新頁面返回頂部

Round #2

公告