浙大第十六届程序设计竞赛总结
2016-04-13 本文已影响133人
moosoo
zoj 3927 Programming Ability Test
题意：四个数的和大于等于80。这么招摇的广告，为了广告效应也得是道水题~~~
#include
#include
#include
#include
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a+b+c+d>=80)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
zoj 3929 Deque and Balls
搬砖的地址： http://blog.csdn.net/doris1104/article/details/51126910
题意：每次等概率地往一个序列的左边或右边放一个球，问期望的相邻逆序对有多少个。
思考出发点：当放入第 i 个球时，恰好在第 j 个球左边/右边的概率是多少？
稍微找一下规律就可以发现：i 号球
和 i – 1 号球相邻的概率是 ½
和 i – 2 号球相邻的概率是 ¼
以此类推，一个例外是与 1 号球相邻的概率和与 2 号球相邻的概率是相同的
做法思路：维护一个数据结构，用于查询比 x 小的元素的概率之和是多少，再维护一个数据结构，查询比 x 大的元素的概率之和是多少，然后把查询的结果加起来
既然如此，那就可以直接用一个数组，查询 x 时，计算不等于 x 的概率就行了
最后答案会乘以 2^n，因此所有的概率都能用整数表示，别算错就行了
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll power[100005];
ll r[100005];
ll dp[100005];
int main(){
power[0]=1;
for(int i=1;i<=100000;i++){
power[i]=(power[i-1]*2)%mod;
}
int t,n,a;
cin>>t;
while(t--){
memset(r,0,sizeof(r));
memset(dp,0,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
dp[i]=(dp[i-1]*2+power[i-2]-r[a]+mod)%mod;
if(i==1)
r[a]=(r[a]+1)%mod;
else
r[a]=(r[a]+power[i-2])%mod;
}
cout<<dp[n]*2%mod<<endl;
}
return 0;
}
zoj 3930 Dice Notation
题意：可以直接看样例的模拟题，但是要注意对换行符的处理。
#include<stdio.h>
#include<string.h>
char tmp[2000000+10],s[2000000+10];
char ans[2000000+10];
char u[2000000+10];
int T,len,f;
int g;
void init(){
memset(tmp,0,sizeof(tmp));
memset(ans,0,sizeof(ans));
memset(s,0,sizeof(s));
len=0;
f=0;
}
void c(){
for(int i=0;tmp[i];i++){
if(tmp[i]=='d'||tmp[i]=='+'||tmp[i]=='-'||tmp[i]=='*'||tmp[i]=='/'||tmp[i]=='('
||tmp[i]==')'||(tmp[i]>='0'&&tmp[i]<='9'))
s[len++]=tmp[i];
}
}
void work(){
int pre=0;
int pos1,pos2;
for(int i=0;s[i];i++){
if(s[i]=='d'){
pos1=i,pos2=i;
for(int j=i+1;s[j];j++){
if(s[j]>='0'&&s[j]<='9')
pos2=j;
else
break;
}
for(int j=i-1;j>=0;j--){
if(s[j]>='0'&&s[j]<='9')
pos1=j;
else
break;
}
int a=0;
for(int j=pos1;j<=i-1;j++)
a=a*10+s[j]-'0';
for(int j=pre;j<pos1;j++)
ans[f++]=s[j];
pre=pos2+1;
memset(u,0,sizeof(u));
g=0;
u[g++]='[';
for(int j=i;j<=pos2;j++)
u[g++]=s[j];
u[g++]=']';
if(a==0)
a=1;
if(a!=1)
ans[f++]='(';
for(int k=0;u[k];k++)
ans[f++]=u[k];
for(int j=1;j<=a-1;j++){
ans[f++]='+';
for(int k=0;u[k];k++)
ans[f++]=u[k];
}
if(a!=1)
ans[f++]=')';
}
}
for(int j=pre;s[j];j++)
ans[f++]=s[j];
}
void print(){
for(int i=0;ans[i];i++){
if(ans[i]=='+'||ans[i]=='-'||ans[i]=='*'||ans[i]=='/')
printf(" %c ",ans[i]);
else
printf("%c",ans[i]);
}
printf(" = [Result]\n");
}
int main(){
scanf("%d",&T);
getchar();
while(T--){
init();
gets(tmp);
c();
work();
print();
}
return 0;
}
zoj 3932 Handshakes
题意：贪心，当前拥有最多朋友的人总能和进来的人握手
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100005],sum[100005];
int main()
{
int t,n,maxx;
scanf("%d",&t);
while(t--)
{
maxx=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
a[n+1]=0;
sum[n+1]=0;
for(int i=n;i>=1;i--)
{
if(a[i+1])
{
sum[i]=sum[i+1]+1;
}
else
sum[i]=sum[i+1];
if(a[i]+sum[i]>maxx)
maxx=a[i]+sum[i];
}
printf("%d\n",maxx);
}
return 0;
}
zoj 3933 Team Formation
题意：有 n 个人，每个人属于 0 组或是 1 组，现在想要组队，每个队伍必须是一个 0 组的人和一个 1 组的组队，问在组队数最多的情况下，队伍中的女生数量最多能有多少个？
解题思路：比较直白的带权匹配问题，权值要设大一点，可以用 KM 算法或是费用流解决，稍微有一些卡模板效率，最好还是用 KM。
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
/* KM算法
* 复杂度O(nx*nx*ny)
* 求最大权匹配
* 若求最小权匹配，可将权值取相反数，结果取相反数
* 点的编号从0开始
*/
const int N = 505;
const int INF = 0x3f3f3f3f;
int nx,ny;//两边的点数 nx,第一队的个数，ny，第二队的个数。注意 nx <= ny，否则会死循环。
int g[N][N];//二分图描述 g[i][j],i属于第一队，j属于第二队。
int linker[N],lx[N],ly[N];//y中各点匹配状态，x,y中的点标号
int slack[N];
bool visx[N],visy[N];
bool DFS(int x)
{
visx[x] = true;
for(int y = 0; y < ny; y++)
{
if(visy[y])continue;
int tmp = lx[x] + ly[y] - g[x][y];
if(tmp == 0)
{
visy[y] = true;
if(linker[y] == -1 || DFS(linker[y]))
{
linker[y] = x;
return true;
}
}
else if(slack[y] > tmp)
slack[y] = tmp;
}
return false;
}
int KM()
{
memset(linker,-1,sizeof(linker));
memset(ly,0,sizeof(ly));
for(int i = 0;i < nx;i++)
{
lx[i] = -INF;
for(int j = 0;j < ny;j++)
if(g[i][j] > lx[i])
lx[i] = g[i][j];
}
for(int x = 0;x < nx;x++)
{
for(int i = 0;i < ny;i++)
slack[i] = INF;
while(true)
{
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(DFS(x))break;
int d = INF;
for(int i = 0;i < ny;i++)
if(!visy[i] && d > slack[i])
d = slack[i];
for(int i = 0;i < nx;i++)
if(visx[i])
lx[i] -= d;
for(int i = 0;i < ny;i++)
{
if(visy[i])ly[i] += d;
else slack[i] -= d;
}
}
}
int res = 0;
for(int i = 0;i < ny;i++)
if(linker[i] != -1)
res += g[linker[i]][i];
return res;
}
int vis[505][505];
int main(){
int t,n,a,m;
cin>>t;
while(t--){
memset(linker,0,sizeof(linker));
memset(g,0,sizeof(g));
memset(vis,0,sizeof(vis));
cin>>n;
string Group,Sex;
cin>>Group>>Sex;
nx=ny=n;
for(int i=0;i<n;i++){
cin>>m;
for (int j = 0; j < m; j++){
cin >> a;
vis[i][a - 1] = 1;
vis[a - 1][i] = 1;
}
for(int j=0;j<n;j++){
if(!vis[i][j]&&!vis[j][i]&&Group[i]!=Group[j]){
int ret=20000;
if(Sex[i]=='0') ret++;
if(Sex[j]=='0') ret++;
if(Group[i]=='0'&&Group[j]=='1') g[i][j]=ret;
else if (Group[i] == '1' && Group[j] == '0') g[j][i] = ret;
}
}
}
int res=KM();
cout<<(res/20000)<<" "<<(res%10000)<<endl;
for(int i=0;i<n;i++){
if(linker[i]!=-1&&g[linker[i]][i]){
cout << linker[i] + 1 << " " << i + 1 << endl;
}
}
}
return 0;
}
zoj 3935 2016
题意：既是三角形数又是六角形数且是闰年的数字
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, n, m;
int main() {
for (int i = 2016, j = 476; i <= 990528; i += j)
{
if (i % 400 == 0 || i % 100 != 0) printf("%d\n", i);
j += 64;
}
return 0;
}
