天天看点
返回

Codeforces Round #368 (Div. 2) 题解Brain’s PhotosBakeryPythagorean TriplesPersistent BookcaseGarlands

  • Brains Photos
  • Bakery
  • Pythagorean Triples
  • Persistent Bookcase
  • Garlands

Brain’s Photos 

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (1000000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=,f=; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
    while(isdigit(ch)) { x=x*+ch-'0'; ch=getchar();}
    return x*f;
} 
int main()
{
//  freopen("A.in","r",stdin);
//  freopen(".out","w",stdout);

    int n=read(),m=read();
    For(i,n) For(j,m) {
        char c[];
        scanf("%s",c);
        if (c[]=='C'||c[]=='M'||c[]=='Y') {
            puts("#Color"); return ;
        }
    }
    puts("#Black&White");
    return ;
}

Bakery 

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (1000000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=,f=; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
    while(isdigit(ch)) { x=x*+ch-'0'; ch=getchar();}
    return x*f;
} 

struct Edge{
    int from,to;
    ll dist;
};
struct HeapNode {
    ll d;
    int u;
    bool operator< (const HeapNode& rhs) const {
        return d > rhs.d;
    }
}; 
#define MAXN (101000)
struct Dijkstra {
    int n,m;
    vector<Edge> edges;
    vector<int> G[MAXN];
    bool done[MAXN];
    ll d[MAXN];
    int p[MAXN]; //×î¶Ì·ÖÐÉÏÒ»Ìõ±ß
    int pnode[MAXN];
    void addedge(int u,int v,ll w){
        edges.pb((Edge){u,v,w});
        G[u].pb(m++);
    }
    void addedge2(int u,int v,ll w) {
        addedge(u,v,w);addedge(v,u,w);
    }
    void init(int _n){
        n=_n; m = ;
        Rep(i,n) G[i].clear();
        edges.clear(); 
    } 
    void dijkstra(int k) {
        priority_queue<HeapNode> Q;
        Rep(i,n) d[i]=(ll),pnode[i]=-;
        MEM(done)
        Rep(i,k) {
            int p=read();
            d[p]=;
            Q.push((HeapNode){,p});
        }
        while(!Q.empty()) {
            HeapNode x=Q.top(); Q.pop();
            int u=x.u;
            if (done[u]) continue;
            done[u]=;
            int mm=G[u].size();
            Rep(i,mm) {
                Edge e = edges[G[u][i]];
                if (d[e.to]>d[u]+e.dist) {
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    pnode[e.to]=u;
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
        ll p=(ll);
        Rep(i,n) if (d[i]!=(ll)&&d[i]>) {
            p=min(p,d[i]) ;
        }
        if (p==(ll))    puts("-1");
        else cout<<p<<endl;
    } 
}S1;
int main()
{
//  freopen("B.in","r",stdin);
//  freopen(".out","w",stdout);

    int n=read(),m=read(),k=read();
    S1.init(+n);
    Rep(i,m){
        int u=read(),v=read(),w=read();
        S1.addedge2(u,v,w);
    }
    if (k==n||k==) {
        puts("-1");
        return ;
    }
    S1.dijkstra(k);

    return ;
}

Pythagorean Triples

公式： (k(n2−m2),2knm,k(n2+m2))

((n2−1)/2,n,(n2+1)/2)(n is odd)

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (1000000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=,f=; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
    while(isdigit(ch)) { x=x*+ch-'0'; ch=getchar();}
    return x*f;
} 
ll m,k;
ll calc(ll &m,ll &k,ll n) {
    if (n%) {
        ll t=(n-)/;
        m=t*t;
        k=(t+)*(t+);
    }
    else {
        calc(m,k,n/);
        m*=;k*=;
    }
}
int main()
{
//  freopen("C.in","r",stdin);
//  freopen(".out","w",stdout);
    ll n=read();
    if (n<=) puts("-1");
    else if (n%==) {
        n=n*n;
        n=(n-)/;
        cout<<n<<' '<<n+<<endl;
        return ;
    } else {
        n/=;
        ll t=,q=n;
        cout<<q*q-t*t<<' '<<q*q+t*t<<endl;
        return ;
    }
    return ;
}

Persistent Bookcase

只需要转移列，和每行对应的列

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (1000000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=,f=; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
    while(isdigit(ch)) { x=x*+ch-'0'; ch=getchar();}
    return x*f;
} 
#define MAXN (1000+10)
#define MAXM (1000+10)
#define MAXQ (100000+10)
int last[MAXQ][MAXN]={},ans[MAXQ]={};
bool rw[MAXQ][MAXM]={};
int main()
{
//  freopen("D.in","r",stdin);
//  freopen(".out","w",stdout);
    int n=read(),m=read(),q=read(); 
    int k;
    For(i,q) {
        int op=read();
        if (op==) {
            k=read();
            copy_n(last[k],n,last[i]); ans[i]=ans[k];
        } else {
            copy_n(last[i-],n,last[i]); ans[i]=ans[i-];
            if (op<=) {
                int a=read(),b=read(); 
                a--,b--;
                copy_n(rw[last[i][a]],m,rw[i]);
                last[i][a]=i;
                if (op==&&rw[i][b]==) ans[i]++,rw[i][b]=;
                if (op==&&rw[i][b]==) ans[i]--,rw[i][b]=;
            } else {
                int a=read();
                a--;
                copy_n(rw[last[i][a]],m,rw[i]);
                last[i][a]=i;
                Rep(j,m) if (rw[i][j]) ans[i]--; else ans[i]++;
                Rep(j,m) rw[i][j]^=;
            }
        }
        cout<<ans[i]<<endl;

    }


    return ;
}

Garlands

时限3秒，二维树状数组暴力修改过。

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (1000000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=,f=; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
    while(isdigit(ch)) { x=x*+ch-'0'; ch=getchar();}
    return x*f;
} 
#define MAXN (2000+10)
int a[MAXN][MAXN],n,m,k;
vector<pi > col[MAXN];
ll f[MAXN][MAXN]={}; 
void add(int x,int y,ll v) {
//  cout<<x<<' '<<y<<' '<<v<<endl;
    for(int i=x;i<=n;i+=i&(-i)) 
        for(int j=y;j<=m;j+=j&(-j)) 
            f[i][j]+=v;
}
ll qur(int x,int y) {
    ll v=;
    for(int i=x;i;i-=i&(-i)) 
        for(int j=y;j;j-=j&(-j)) 
            v+=f[i][j];
    return v;
}
bool b[MAXN]={},la[MAXN]={};
int main()
{
//  freopen("E.in","r",stdin);
//  freopen(".out","w",stdout);

    n=read(),m=read(),k=read();
    For(i,k) {
        int t=read();
        Rep(j,t) {
            int u=read(),v=read();
            a[u][v]=read();
            col[i].pb(mp(u,v)); 
        }
        la[i]=;
    }   
    int q=read();
    while(q--) {
        string s;
        cin>>s;
        if (s[]=='A') {
            For(i,k) if (la[i]^b[i]) {
                b[i]^=;
                Rep(j,SI(col[i])) add(col[i][j].fi,col[i][j].se,(la[i]?:-)*a[col[i][j].fi][col[i][j].se]);
            }
            int x1=read(),y1=read(),x2=read(),y2=read();
            cout<<qur(x2,y2)-qur(x1-,y2)-qur(x2,y1-)+qur(x1-,y1-)<<endl;
        } else {
            la[read()]^=;
        }
    }
    return ;
}
比赛题解
上一篇: 镜头基础知识及选型1.镜头的结构及原理2.镜头的基本参数3. 远心镜头4. 镜头的选型
下一篇: matlab 镜头晃动,ScaramuzzaOCamCalib 鱼眼镜头拍摄时会有畸变，此matlab工具箱具有校正图像 的功能，也可以进行多个相机 Special Effects 图形 处理 238...

继续阅读