2013“嘉杰信息”杯ACM/ICPC湘潭多省程序设计竞赛暨湘潭市第五届大学生程序设计竞赛
2013年湘潭市大学生程序设计竞赛 题解：
题目：
Alice and Bob |
||
| Accepted : 7 | Submit : 37 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
Problem DescriptionAlice and Bob always love to play games, so does this time. InputMultiple test cases. First line, there is an integer T ( 1 ≤ T ≤ 20 ), indicating the number of test cases. OuputFor each test case, output a line. It is an integer number k, indicating the least number of operation in need to finish the task. Sample Input5 1 2 3 4 5 Sample Output1 1 2 1 2 |
dp题。我是bfs做的。比赛的时候deburg 了很久。蛋疼的题目和水货。。。
可以测试数据： 6422.正确为4.a取1024，b取2187，a取1024.b取2187.
#include<cstdlib>
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define INF 999999
int s[50022][2];
int in[50022];
int n;
int a[100]={1,2,4,8,16};
int b[100]={1,3,9,27};
int num2=4;
int num3=3;
queue<int>q;
void dabiao()
{
while(a[num2-1] * 2 <= 20099){
a[num2] = a[num2 - 1] * 2;
num2++;
}
while(b[num3-1]*3 < 20099){
b[num3] = b[num3-1] *3;
num3++;
}
}
void bfs()
{
while(!q.empty()) q.pop();
int j,f,t,v;
for(j=0;j<=14055;j++)
for(int k=0;k<2;k++)
s[j][k]=INF;
for(j=0;a[j]<=14011;j++){
s[a[j]] [0] =1;
q.push(1);
q.push(a[j]);
}
while(!q.empty()){
f=q.front(); q.pop();
t=q.front(); q.pop();
// if(t== 1024 || t== 2187|| t==1024+2187|| t==1024*2+2187*2)
// cout<<t<<" "<<f<<endl;
if(f)
for(j=0;t+b[j] <=14011;j++){
v=t+b[j];
if(s[v][1] > s[t][0]+1){
s[v][1] = s[t][0] +1;
q.push(0);
q.push(v);
}
}
else
for(j=0;t+a[j] <14011;j++){
v=t+a[j];
if(s[v][0] >s[t][1] + 1){
s[v][0] =s[t][1] + 1;
q.push(1);
q.push(v);
}
}
}
}
int main()
{
int t;
dabiao();
bfs();
scanf("%d", &t);
while(t--){
scanf("%d", &n);
printf("%d\n" ,min(s[n][0], s[n][1]));
}
return 0;
}
Binary Search Tree |
||
| Accepted : 7 | Submit : 23 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
Problem DescriptionIn computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties: InputMultiple test cases. First line, an integer T ( 1 ≤ T ≤ 20 ), indicating the number of test cases. OuputFor each test case, output a line. The answer is an integer m ( 0 <= m <= n - 1 ), indicating the least number of nodes we have to modify. Sample Input2 3 2 2 3 3 0 0 1 0 0 2 10 0 2 15 0 0 Sample Output2 0 HintFor test case 1, we can modify the key of node #2 to 1, and modify the key of node #3 to 3.
SourceXTU OnlineJudge |
b题，dfs找根节点。再求最长上升公共子序列的长度。
f，连最长公共上升子序列都忘记求了。初始化错误。。。。
#include<cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int num,n;
int a[10099];
int flag[10099];
int l[10099],r[10099],v[10099];
int dp[10099];
void dfs(int x)
{
if(x== 0)
return;
dfs(l[x]);
a[num++]= v[x];
dfs(r[x]);
// flag[l[x]] = flag[r[x]] = flag[x] = 1;
}
void find_root(int x)
{
if(flag[x] ==1 || x==0){
return ;
}
flag[x] =1;
find_root(l[x]);
find_root(r[x]);
}
int main()
{
int tt,vv,ll,rr,ans,j,root;
scanf("%d", &tt);
while(tt--){
scanf("%d", &n);
for(j=1;j<=n;j++){
scanf("%d %d %d", &v[j],&l[j],&r[j]);
}
memset(flag, 0, sizeof(flag));
for(j=1;j<=n;j++)
if(flag[j]== 0){
root=j;
find_root(j);
}
// cout<<"\t root is \t "<< root<<endl <<endl;
num=0;
dfs(root);
////
//// for(j=0;j<n;j++)
//// cout<<a[j]<<"\t";
//// cout<<endl;
////
//// cout<<endl<<endl;
for(j=0;j<n;j++)
dp[j]=1;
for(int j=1;j<n;j++)
for(int k=j-1;k>=0;k--)
if(a[j]>a[k] && dp[j] < dp[k] +1)
dp[j]=dp[k] + 1;
cout<<n-*max_element(dp,dp+n)<<endl;
}
}