传送门
这场比赛是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>
![图解elasticsearch的_source、_all、store和index[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)