2018-08-13

multi-university contest7

数论快速入门

acm的数论的课件刷一遍

unodered_map

1010 矩阵分块乘法

注意每一个分块矩阵的大小为p/(p/i),全部为整除

ac code

#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
struct jz
{
	long long num[3][3];
	jz() { memset(num,0,sizeof(num)); }
	jz operator*(const jz &P)const
	{
		jz ans;
		for(int k=0;k<3;k++)
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					ans.num[i][j]=(ans.num[i][j]+num[i][k]*P.num[k][j]%mod)%mod;
		return ans;
	}
}COE,ans,unit;
int T_T;
long long A,B,C,D,P,n;
jz pOw(jz X,long long m)
{
	jz ans;
	for(ans=unit;m;m>>=1,X=X*X)
		if(m&1)
			ans=ans*X;
	return ans;
}
void init(long long A,long long B,long long C,long long D,long long x)
{
	COE.num[1][0]=1;
	COE.num[1][1]=0;
	COE.num[1][2]=0;
	COE.num[0][0]=D;
	COE.num[0][1]=C;
	COE.num[0][2]=x; // this element need to be changed each step.
	COE.num[2][0]=0;
	COE.num[2][1]=0;
	COE.num[2][2]=1;
	return;
}
int main()
{
	for(int i=0;i<3;i++) unit.num[i][i]=1;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&P,&n);
		if(n==1) printf("%lld\n",A);
		else if(n<P)
		{
			ans.num[0][0]=B;
			ans.num[1][0]=A;
			ans.num[2][0]=1;
			//P/(P/i)相当于下一次x变化的i的下标
			for(long long i=3;i<=n;i=P/(P/i)+1)
			{
				init(A,B,C,D,P/i);
				if(n<=P/(P/i)) COE=pOw(COE,n-i+1);
				else COE=pOw(COE,P/(P/i)+1-i);
				ans=COE*ans;
			}
			printf("%lld\n",ans.num[0][0]);
		}
		else if(P<=n)
		{
			ans.num[0][0]=B;
			ans.num[1][0]=A;
			ans.num[2][0]=1;
			for(long long i=3;i<=P;i=P/(P/i)+1)
			{
				init(A,B,C,D,P/i);
				COE=pOw(COE,P/(P/i)+1-i);
				ans=COE*ans;
			}
			init(A,B,C,D,0);
			COE.num[0][2]=0;
			COE.num[2][0]=0;
			ans.num[2][2] = 0;
			COE=pOw(COE,n-max(P,2LL));
			ans=COE*ans;
			printf("%lld\n",ans.num[0][0]);
		}
	}
	return 0;
}

fastread

namespace fastIO {
	#define BUF_SIZE 100000
	//fread -> read
	bool IOerror = 0;
	inline char nc() {
		static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			if(pend == p1) {
				IOerror = 1;
				return -1;
			}
		}
		return *p1++;
	}
	inline bool blank(char ch) {
		return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
	}
	inline void read(int &x) {
		char ch;
		while(blank(ch = nc()));
		if(IOerror) return;
		for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
	}
	#undef BUF_SIZE
};
using namespace fastIO;

A

每一个节点保存最优的边的编号，注意会有更新的顺序问题，所以要么重载pq,要么扫描两遍，扫两遍用了超级读入挂
学长的写法

ac code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
int INF = 1e9;
struct Edge{
    int to;
    int id;
}edge[maxn];
int n, m, s;
vector<Edge> G[maxn];
typedef pair<int, int> P;//第一维保存最短距离，第二维保存点标
set<int> pre[maxn];
int dis[maxn];
set<int>::iterator it;
int ans[maxn];
int tot;
bool vis[maxn];
namespace fastIO {
	#define BUF_SIZE 100000
	//fread -> read
	bool IOerror = 0;
	inline char nc() {
		static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			if(pend == p1){
				IOerror = 1;
				return -1;
			}
		}
		return *p1++;
	}
	inline bool blank(char ch) {
		return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
	}
	template<class T>
	inline bool read(T &x) {
		char ch;
		while(blank(ch = nc()));
		if(IOerror)
			return false;
		for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
		return true;
	}
	#undef BUF_SIZE
};
using namespace fastIO;
void Dijkstr(){
    priority_queue<P, vector<P>, greater<P> > pq;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for(int i=0; i<G[s].size(); i++){
        int v = G[s][i].to;
        pq.push(P(s, v));
        dis[v] = 1;
        pre[v].insert(G[s][i].id);
    }
    while(!pq.empty()){
        P p = pq.top();
        pq.pop();
        int u = p.second;
        //if(dis[u]<p.first) continue;
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].to;
            if(dis[v]>dis[u]+1&&pre[u].count(G[u][i].id) == 0){
                dis[v] = dis[u]+1;
                pq.push(P(dis[v], v));
                pre[v].clear();
                pre[v].insert(G[u][i].id);
            }
            else if(dis[v] == dis[u]+1&&pre[u].count(G[u][i].id) == 0){
                pre[v].insert(G[u][i].id);
                //pq.push(P(dis[v], v));
            }
            else if(pre[u].count(G[u][i].id)&&dis[v]>dis[u]){
                dis[v] = dis[u];
                pre[v].clear();
                pre[v].insert(G[u][i].id);
                pq.push(P(dis[v], v));
            }
            else if(pre[u].count(G[u][i].id)&&dis[v] == dis[u]){
                pre[v].insert(G[u][i].id);
                //pq.push(P(dis[v], v));
            }
        }
    }
}
#define ENABLE_FREAD
namespace io_impl
{
inline bool maybe_digit(char c)
{
    return c >= '0' && c <= '9';
}
inline bool maybe_decimal(char c)
{
    return (c >= '0' && c <= '9') || (c == '.');
}
struct io_s
{
    bool negative;
    bool ok = true;
    char ch = next_char();
    int precious = 6;
    long double epslion = 1e-6;
#ifdef ENABLE_FREAD
    inline char next_char()
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }
#else
    inline char next_char() const
    {
        return getchar();
    }
#endif
    /// read int
    template <typename T>
    inline bool rn(T& _v)
    {
        negative = false;
        _v = 0;
        while (!maybe_digit(ch) && ch != EOF)
        {
            negative = ch == '-';
            ch = next_char();
        };
        if (ch == EOF) return ok = false;
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
        if (negative) _v = -_v;
        return true;
    }
    template <typename T>
    inline void rn_unsafe(T& _v)
    {
        negative = false;
        _v = 0;
        while (!maybe_digit(ch))
        {
            negative = ch == '-';
            ch = next_char();
        };
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
        if (negative) _v = -_v;
    }
    template <typename T>
    inline T rn()
    {
        T v = T();
        rn_unsafe(v);
        return v;
    }
    inline int ri() { return rn<int>(); }
    inline ll rll() { return rn<ll>(); }
    /// read unsigned
    template <typename T>
    inline bool run(T& _v)
    {
        _v = 0;
        while (!maybe_digit(ch) && ch != EOF) ch = next_char();
        if (ch == EOF) return ok = false;
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
        return true;
    }
    template <typename T>
    inline void run_unsafe(T& _v)
    {
        _v = 0;
        while (!maybe_digit(ch)) ch = next_char();
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
    }
    template <typename T>
    inline T run()
    {
        T v = T();
        run_unsafe(v);
        return v;
    }
    /// read double
    template <typename T>
    inline bool rd(T& _v)
    {
        negative = false;
        _v = 0;
        while (!maybe_digit(ch) && ch != EOF)
        {
            negative = ch == '-';
            ch = next_char();
        };
        if (ch == EOF) return ok = false;
        do
        {
            _v = (_v * 10) + (ch - '0');
        } while (maybe_digit(ch = next_char()));
        static int stk[70], tp;
        if (ch == '.')
        {
            tp = 0;
            T _v2 = 0;
            while (maybe_digit(ch = next_char()))
            {
                stk[tp++] = ch - '0';
            }
            while (tp--)
            {
                _v2 = _v2 / 10 + stk[tp];
            }
            _v += _v2 / 10;
        }
        if (ch == 'e' || ch == 'E')
        {
            ch = next_char();
            static bool _neg = false;
            if (ch == '+')
                ch = next_char();
            else if (ch == '-')
                _neg = true, ch = next_char();
            if (maybe_digit(ch))
            {
                _v *= pow(10, run<ll>() * (_neg ? -1 : 1));
            }
        }
        if (negative) _v = -_v;
        return true;
    }
    template <typename T>
    inline T rd()
    {
        T v = T();
        rd(v);
        return v;
    }
    /// read string
    inline int gets(char* s)
    {
        char* c = s;
        while (ch == '\n' || ch == '\r' || ch == ' ') ch = next_char();
        if (ch == EOF) return (ok = false), *c = 0;
        do
        {
            *(c++) = ch;
            ch = next_char();
        } while (ch != '\n' && ch != '\r' && ch != ' ' && ch != EOF);
        *(c++) = '\0';
        return static_cast<int>(c - s - 1);
    }
    inline int getline(char* s)
    {
        char* c = s;
        while (ch == '\n' || ch == '\r') ch = next_char();
        if (ch == EOF) return (ok = false), *c = 0;
        do
        {
            *(c++) = ch;
            ch = next_char();
        } while (ch != '\n' && ch != '\r' && ch != EOF);
        *(c++) = '\0';
        return static_cast<int>(c - s - 1);
    }
    inline char get_alpha()
    {
        while (!isalpha(ch)) ch = next_char();
        const char ret = ch;
        ch = next_char();
        return ret;
    }
    inline char get_nonblank()
    {
        while (isblank(ch)) ch = next_char();
        const char ret = ch;
        ch = next_char();
        return ret;
    }
    inline char get_char()
    {
        const char ret = ch;
        ch = next_char();
        return ret;
    }
    template <typename T>
    inline void o(T p)
    {
        static int stk[70], tp;
        if (p == 0)
        {
            putchar('0');
            return;
        }
        if (p < 0)
        {
            p = -p;
            putchar('-');
        }
        while (p) stk[++tp] = p % 10, p /= 10;
        while (tp) putchar(stk[tp--] + '0');
    }
    template <typename T>
    inline void od(T v)
    {
        static int stk[70], tp;
        tp = 0;
        if (fabs(v) < epslion / 10)
        {
            putchar('0');
            if (precious > 0)
            {
                putchar('.');
                for (int i = 0; i < precious; ++i) putchar('0');
            }
            return;
        }
        else
        {
            if (v < 0)
            {
                v = -v;
                putchar('-');
            }
            v += epslion / 2;
            T p = floor(v) + epslion / 10;
            while (fabs(p) > 1 - epslion)
            {
                stk[++tp] = fmod(p, 10), p /= 10;
            }
            while (tp) putchar(stk[tp--] + '0');
        }
        if (precious == 0) return;
        putchar('.');
        v -= floor(v);
        for (int i = 0; i < precious; ++i)
        {
            v *= 10;
            putchar((int)floor(v) + '0');
            v = fmod(v, 1);
        }
    }
    /// Enhancement
    typedef void io_operator(io_s& v);
    typedef char* charptr;
    template <typename T>
    inline io_s& operator>>(T& x)
    {
        if (numeric_limits<T>::is_signed)
            rn(x);
        else
            run(x);
        return *this;
    }
    template <typename T>
    inline io_s& operator<<(const T& x);
    inline io_s& operator<<(io_operator* v)
    {
        v(*this);
        return *this;
    }
    operator bool() const { return ok; }
    void set_precious(int x)
    {
        precious = x;
        epslion = pow(10, -x);
    }
};
template <>
inline io_s& io_s::operator>>(char*& x)
{
    gets(x);
    return *this;
}
template <>
inline io_s& io_s::operator>>(float& x)
{
    rd(x);
    return *this;
}
template <>
inline io_s& io_s::operator>>(double& x)
{
    rd(x);
    return *this;
}
template <>
inline io_s& io_s::operator>>(long double& x)
{
    rd(x);
    return *this;
}
template <>
inline void io_s::o(const char* p)
{
    printf(p);
}
template <>
inline void io_s::o(const char p)
{
    putchar(p);
}
template <>
inline void io_s::o(float p)
{
    od(p);
}
template <>
inline void io_s::o(double p)
{
    od(p);
}
template <>
inline void io_s::o(long double p)
{
    od(p);
}
template <typename T>
inline io_s& io_s::operator<<(const T& x)
{
    o(x);
    return *this;
}
inline void new_line(io_s& v)
{
    v.o('\n');
}
io_s::io_operator* nl = new_line;
} // namespace io_impl
using namespace io_impl;
io_s io;
int main()
{
    while(io>>n>>m){
        int u, v, weight;
        Edge temp;
        for(int i=0; i<maxn; i++)G[i].clear(), pre[i].clear();
        for(int i=0; i<m; i++){
            io>>u>>v>>weight;
            temp.to = v, temp.id = weight;
            G[u].push_back(temp);
            temp.to = u;
            G[v].push_back(temp);
        }
        s = 1;
        Dijkstr();
        int ans = dis[n];
        for(int i=0; i<n+1; i++) pre[i].clear();
        s = n;
        Dijkstr();
        ans = min(ans, dis[1]);
        if(ans == 0x3f3f3f3f) io<<"-1"<<nl;
        else io<<ans<<nl;
    }
    return 0;
}

1011 swordman

模拟银行家算法
原来用5个set暴力来保存会T

ac code

#include<bits/stdc++.h>
using namespace std;
namespace fastIO {
	#define BUF_SIZE 100000
	//fread -> read
	bool IOerror = 0;
	inline char nc() {
		static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			if(pend == p1) {
				IOerror = 1;
				return -1;
			}
		}
		return *p1++;
	}
	inline bool blank(char ch) {
		return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
	}
	inline void read(int &x) {
		char ch;
		while(blank(ch = nc()));
		if(IOerror) return;
		for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
	}
	#undef BUF_SIZE
};
using namespace fastIO;
typedef pair<int, int> P;
typedef priority_queue<P, vector<P>, greater<P> > PQ;
const int maxn = 5e5+10;
int a[maxn][6], b[maxn][6];
int n, k;
int att[6];
PQ pq[6];
int main()
{
    int _;
    read(_);
    while(_--){
        //cin>>n>>k;
        read(n), read(k);
        int tot = 0;
        for(int i=1; i<=k; i++) read(att[i]);
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=k; j++) read(a[i][j]);
            for(int j=1; j<=k; j++) read(b[i][j]);
        }
        for(int i=1; i<=k; i++) while(!pq[i].empty()) pq[i].pop();
        for(int i=1; i<=n; i++) pq[1].push(P(a[i][1], i));
        while(true){
            bool change  = false;
            for(int i=2; i<=k; i++){
                while(!pq[i-1].empty()){
                    int w = pq[i-1].top().first;
                    int id = pq[i-1].top().second;
                    if(w<=att[i-1]){
                        pq[i].push(P(a[id][i], id));
                        pq[i-1].pop();
                    }
                    else break;
                }
            }
            while(!pq[k].empty()){
                int w = pq[k].top().first;
                int id = pq[k].top().second;
                if(att[k]>=w){
                    for(int j=1; j<=k; j++){
                        att[j] += b[id][j];
                    }
                    change = true;
                    pq[k].pop();
                    tot++;
                }
                else break;
            }
            if(!change) break;
        }
        printf("%d\n", tot);
        for(int i=1; i<k; i++) printf("%d ", att[i]);
        printf("%d\n", att[k]);
    }
    return 0;
}

BZOJ 1453

未解决的问题

本文标题:multi-university contest7

文章作者:Babydragon

发布时间:2018-08-13, 17:09:43

最后更新:2018-08-14, 13:46:28

原始链接:http://baolintian.github.io/2018/08/13/multi-university-contest7/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。