天天看點
傳回

2015 UESTC Winter Training #9

傳送門

這場比賽是2010東京區域賽的題目，隻做了幾題簡單的題目

Aizu 1305 Membership Management

題意：給你幾個部門的人，一個部門可能包含于另一個部門之下

問：第一個部門有多少人

用map給每個部門編号，然後set數組存每個部門人名，然後用dfs搜尋答案

<span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")


using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;

#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1;
    char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

map<string,int> g;
set<string> ss[101],ans;
int n,vis[101];

void init(int n)
{
	g.clear();ans.clear();
	for(int i=1;i<=n;i++)
		ss[i].clear();
	CLR(vis,0);
}

void dfs(int i)
{
	vis[i]=1;
	for(set<string>::iterator it=ss[i].begin();it!=ss[i].end();it++)
	{
		if(g.count(*it))
		{
			if(!vis[g[*it]])
				dfs(g[*it]);
		}
		else
			ans.insert(*it);
	}
}

int main()
{
//	freopen("data.txt","r",stdin);
	string str;
	while(read(n)&&n)
	{	
		init(n);
		for(int i=1;i<=n;i++)
		{
			cin>>str;str[str.length()-1]=','; 
			int pos=str.find(':');
			string temp=str.substr(0,pos);
			g[temp]=i;//cout<<temp<<endl;
			while(1)
			{
                str=str.substr(pos+1);
                pos=str.find(',');
                if(pos==-1)
					break;
				temp=str.substr(0,pos);
                ss[i].insert(temp);
            }
		}
		dfs(1);
		write(ans.size()),putchar('\n');
	}
	return 0;
}</span>

Aizu 1306 Balloon Collecting

題意：n氣球從上往下掉，給你掉落的位置和掉落的時間，給你一個初始位置在0的車，去接氣球，最多可以裝3個氣球，就必須傳回0點去放氣球，機關速度為氣球數 k+1

問：如果可以将氣球全部接住，求最短距離；如果不能将氣球全部接住，求第一個接不住的氣球編号

簡單dp，dp[i][j]表示第i個氣球的時候，車上有j個氣球時候的最短距離

這個轉移很好搞定，見代碼

<span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")


using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;

#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1;
    char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

struct Node
{
	int t,p;
	Node(const int& p=0,const int& t=0):t(t),p(p){}
}b[44];
int dp[44][4];

int main()
{
//	freopen("data.txt","r",stdin);
	int n;
	while(read(n)&&n)
	{
		CLR(dp,INF);
		dp[0][0]=0;
		bool flag=0;
		for(int i=1;i<=n;i++)
		{
			read(b[i].p),read(b[i].t);
			if(flag)	continue;
			int dis=abs(b[i].p-b[i-1].p);
			int tim=b[i].t-b[i-1].t;
			for(int j=1;j<=3;j++)
				if(dis*j<=tim)
					dp[i][j]=min(dp[i][j],dp[i-1][j-1]+dis);
			for(int j=1;j<=3;j++)
				if(b[i].p+b[i-1].p*(j+1)<=tim)
					dp[i][1]=min(dp[i][1],dp[i-1][j]+b[i-1].p+b[i].p);
			int minn=INF;
			for(int j=1;j<=3;j++)
            {
               minn=min(minn,dp[i][j]);
//               cout<<dp[i][j]<<" ";
            }
//            cout<<endl;
			if(minn==INF)
			{
				flag=1;
				printf("NG %d\n",i);
			}
		}
		if(!flag)
		{
			int ans=INF;
			for(int i=1;i<=3;i++)
				ans=min(ans,dp[n][i]+b[n].p);
			printf("OK %d\n",ans);
		}
	}
	return 0;
}</span>

Aizu 1308 Awkward Lights

題意：給你一個n*m的01矩陣，然後開關燈，給你一個d，翻轉開關的時候，以開關為中心的曼哈頓距離為d的開關全部翻轉

問：可否全部關燈完畢

高斯消元解異或方程組，如果不可解則說明不行

<span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")


using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;

#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1;
    char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

const int MAXN=26*26;

int b[MAXN][MAXN],ans[MAXN];
int a[MAXN][MAXN];

bool Guass(int n)  
{  
    int i,j,row,col;  
    for(row=0,col=0;row<n && col<n;row++,col++)  
    {    
        for(i=row;i<n;i++)
            if(a[i][col]!=0)  
                break;  
        for(j=col;j<=n && i!=n && i!=row;j++)
            swap(a[row][j],a[i][j]);
		if(!a[row][col])
		{
			row--;continue;
		} 
        for(i=row+1;i<n;i++)  
            if(a[i][col])  
                for(j=col+1;j<=n;j++)  
                    a[i][j]=a[row][j]^a[i][j];  
    }  
    for(i=row;i<n;i++)  
        if(a[i][n])
			return 0;
	return 1; 
} 



int main()
{
//	freopen("data.txt","r",stdin);
	int n,m,d;
	while(read(m)&&read(n)&&read(d)&&(n+m+d))
	{
		CLR(a,0);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				read(b[i][j]);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				a[i*m+j][n*m]=b[i][j];
				a[i*m+j][i*m+j]=1;
				for(int x=0;x<n;x++)
					for(int y=0;y<m;y++)
						if(abs(x-i)+abs(y-j)==d)
							a[i*m+j][x*m+y]=1;
			}
		if(Guass(n*m))
			puts("1");
		else
			puts("0");
	}
	return 0;
}</span>

Aizu 1310 Find the Multiples

題意：給你一個a[0]~a[n-1]的數組，二進制組(i,j)表示a[i]~a[j]的一個數，可以認為是一個十進制的數

問：有多少給(i,j)截取的數，是素數Q的倍數

暴搜會TLE

首先，我們考慮A=(i,j)和B=(I,j)其中I<i，那麼數字B-A，則會得到一個有多個字尾零的數，那麼如果，B，A mod Q的餘數相同，則相減之後，B-A再除以10的幂，就為(I,i)就可以整除Q

那麼當10不能整除Q的時候，就可以直接用B-A來代替二進制組(I,i)來計算，進而變成一維的解法

那麼當Q是2或者5的時候，10可以整除Q，那麼就要單獨計算

<span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")


using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;

#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1;
    char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

const int MAXN=100010;
ll n,s,p,w;

map<ll,ll> ma;
ll a[MAXN];

int main()
{
//	freopen("data.txt","r",stdin);
	while(read(n)&&read(s)&&read(w)&&read(p)&&(n+s+p+w))
	{
		ma.clear();
		int g=s,ans=0,num=0;
	    for(int i=0; i<n; i++) {
	        a[i] = (g/7) % 10;
	        if( g%2 == 0 ) { g = (g/2); }
	        else           { g = (g/2) ^ w; }
	    }
	    if(p==2 || p==5)
	    {
    		for(int i=0;i<n;i++)
    		{
		    	if(a[i])	num++;
	    		if(a[i]%p==0)	ans+=num;
		    }
    	}
    	else
    	{
    		int t=1;
	    	for(int i=n-1;i>=0;i--)
	    	{
	    		num=(a[i]*t+num)%p;
	    		if(a[i])	ans+=ma[num];
	    		ma[num]++;
	    		if(a[i] && num==0)	ans++;
	    		t=(t*10)%p;
	    	}
	    }
	    write(ans),putchar('\n');
    	continue;
	}
	
}</span>

Aizu 1311 Test Case Tweaking

題意：給你一個圖，一個數C

問：最少修改多少條邊使得圖的最短路等于C，保證原先的最短路大于等于C

圖上DP，dp[i][j]表示在i節點的時候，修改j次之後最短的距離

轉移當這次不修改的時候，則在同一個j下面轉移 dp[i][j] = min( dp[u][j] + g[u][i] )

當修改這條邊的時候，則直接将其修改成0，dp[i][j] = min( dp[u][j-1] )

最後到達n點，則如果最短距離小于C，則認為中間有一些改成0的減太多了，稍微加一些就可以達到C，則滿足題意

<span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")


using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;

#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1;
    char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

const int MAXN=111;

int g[MAXN][MAXN],dp[MAXN][MAXN];
bool vis[MAXN];
int n,m,c;

void spfa()
{
    CLR(vis,0);
    queue<int> q;
    q.push(1);
    dp[1][0]=0;
    vis[1]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=1; i<=n; i++)
        {
            if(~g[u][i])
            {
                for(int j=0; j<=n; j++)
                {
                    if(dp[u][j]+g[u][i]<dp[i][j])
                    {
                        dp[i][j]=dp[u][j]+g[u][i];
                        if(!vis[i])
                        {
                            q.push(i);
                            vis[i]=1;
                        }
                    }
                    if(j && dp[u][j-1]<dp[i][j])
                    {
                        dp[i][j]=dp[u][j-1];
                        if(!vis[i])
                        {
                            q.push(i);
                            vis[i]=1;
                        }
                    }
                }
            }
        }
    }
}
int main()
{
//    freopen("data.txt","r",stdin);
    while(read(n)&&read(m)&&read(c)&&(n+m+c))
    {
        CLR(g,-1);
        CLR(dp,INF);
        for(int i=0,u,v,dis; i<m; i++)
        {
            read(u),read(v),read(dis);
            g[u][v]=dis;
        }
        spfa();
        for(int i=0; i<=n; i++)
            if(dp[n][i]<=c)
            {
                printf("%d\n",i);
                break;
            }
    }
    return 0;
}</span>
動态規劃 &amp; 貪心 數學 &amp; 博弈論 &amp; FFT &amp; 位運算 圖論 &amp; 網絡流 搜尋
上一篇: 插件化的基石 -- apk動态加載
下一篇: Android 插件化開發——宿主APP加載APK插件

繼續閱讀