转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
第一次进入DIV1,果断被虐,没法下手。赛后先把DIV2解决了吧
A. System of Equations
问a*a+b=m a+b*b=n,的解a,b,有多少组,因为a,b都非负,而且m和n的范围在1000以内,直接暴力,1000*1000即可
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 55
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
int cnt=0;
for(int i=0;i<=1000;i++)
for(int j=0;j<=1000;j++)
if(i*i+j==n&&j*j+i==m)
cnt++;
printf("%d\n",cnt);
}
return 0;
}
B. Hometask
由一些数字组成一个整数,能整除2,3,5,而且要最大的。
能同时整除2,5的,末位必然是0,能整除3的,所有位数和必为3的倍数。
首先判断是否有0,如果没有则输出-1.
将所有数字降序排列(因为题目要求最大的整数)
接下来看所有位数和是否为3的倍数,如果是,按顺序输出。
接下来就可能会删除某些数字,删除一位肯定比删除两位要大,而且只可能删除一位或者两位。
如果数字和模3为1,则删除一个尽可能小的,模3为1的数,for(int i=1;i<10;i+=3),如果存在一个这样的数,删除
如果不存在,则接下来可能是删除两位的,而且删除的两位模3都为2,从小往大的找,删除两位
如果数字和模3为2,则删除一个尽可能小的,模3为2的数,for(int i=2;i<10;i+=3),如果存在一个这样的数,删除
如果不存在,则接下来可能是删除两位的,而且删除的两位模3都为1,从小往大的找,删除两位
如果上述情况都不存在,则输出-1
在处理的时候,注意别输出000000就行了,包括删除之后的输出。
代码很shi,就不贴了
C. Game
DIV1的A题,还以为网络流,一直在建图,弱爆了。
可以发现1->2 2->3 3->1为1,其余为2,其实就是循环右移一位是1,两位就是2。
加上一点小贪心,枚举第一台机器,首先将能做的都做了,而且把接下来没有限制的都加入队列
如果这台机器没有任务可做,则到下一台,时间+1,直到所有任务完成。也就是选了一台机子之后,先把能做的全都做了,避免转移花费,而且在做了一个任务之后,要把其它没有限制的加入队列。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 55
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
bool mat[205][205];
int c[205],n;
int slove(int s){
int deg[205];
memset(deg,0,sizeof(deg));
queue<int>que[3];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(mat[i][j])
deg[i]++;
if(deg[i]==0)
que[c[i]].push(i);
}
int ret=0,cnt=n;
bool flag[205];
memset(flag,true,sizeof(flag));
while(!que[0].empty()||!que[1].empty()||!que[2].empty()){
if(que[s].empty()) {s=(s+1)%3;ret++;continue;}
int u=que[s].front();
que[s].pop();
cnt--;
flag[u]=false;
for(int i=1;i<=n;i++){
if(mat[i][u]){
deg[i]--;
if(deg[i]==0&&flag[i])
que[c[i]].push(i);
}
}
if(cnt==0)
break;
}
return ret;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
c[i]--;
}
for(int i=1;i<=n;i++){
int k,u;
scanf("%d",&k);
while(k--){
scanf("%d",&u);
mat[i][u]=true;
}
}
int ans=inf;
for(int i=0;i<3;i++)
ans=min(ans,slove(i)+n);
printf("%d\n",ans);
}
return 0;
}
D. Numbers
组合计数。由于不能出现前导0,我们倒序考虑。从9到0,dp[i][j]表示考虑了数字i,长度为j的种数。
然后枚举当前数字取的位数,注意下限,在代码中,表示j位,当前数字i取j-k个 。则之前的取k个,那么就是dp[i+1][k]*c[j][k] 前者是上一轮的种数,后者表示从j个位置 中取出k个放之前的,那么剩下的j-k位放当前数字。
注意数字0的情况要特殊点, 不能有前导0
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 305
#define inf 1<<29
#define MOD 1000000007
#define Max 301
#define LL __int64
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
LL dp[11][205],c[205][205];
int n,a[10];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<10;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
memset(dp,0,sizeof(dp));
dp[10][0]=1;
for(int i=9;i>=0;i--){
for(int j=n;j>=0;j--)
for(int k=j-a[i];k>=0;k--)
if(i) dp[i][j]=(dp[i][j]+dp[i+1][k]*c[j][k])%MOD;
else if(j&&k) dp[i][j]=(dp[i][j]+dp[i+1][k]*c[j-1][k-1])%MOD;
}
LL ans=0;
for(int i=0;i<=n;i++)
ans=(ans+dp[0][i])%MOD;
printf("%I64d\n",ans);
}
return 0;
}
E. Relay Race
NOIP 2008 传纸条,单向很简单,双向的可以考虑成两个人同时从(1,1)到(n,n)。那么用四维的表示两个人的位置就行了,但是这题N达到300,四维的不行。
由于两个人同时在移动,所以x1+y1=x2+y2。那么可以省去一维,我们还可以用dp[i][j][k]表示走了i步,两个人分别是第j行,第k行,则第一个人在i-j+2列,第二个人在i-k+2列。
转移的时候注意不要交叉,而且到达同一位置的时候不能多取。
可能为负,注意初始化
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 305
#define inf 1<<29
#define MOD 9973
#define Max 301
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
int dp[N<<1][N][N];
int a[N][N],n;
int way[4][2]={{0,0},{0,1},{1,0},{1,1}};
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(dp,0x81,sizeof(dp));
dp[0][1][1]=a[1][1];
for(int i=1;i<=2*n-2;i++)
for(int j=1;j<=i+1&&j<=n;j++)
for(int k=j;k<=i+1&&k<=n;k++){
for(int r=0;r<4;r++)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-way[r][0]][k-way[r][1]]);
dp[i][j][k]+=a[j][i-j+2]+a[k][i-k+2]-(j==k?a[k][i-k+2]:0);
}
printf("%d\n",dp[2*n-2][n][n]);
}
return 0;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
-2,4,5,5,6,8 要输出的序列应该是每次从前面选一个,然后从后面选一个 -2,8,4,6,5,5 然后把该序列倒着输出即可 代码: #include #include #include #include #include #include #include #include #...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...