PROB Preface Numbering [ANALYSIS] ---- 又是枚举，让我不得不相信枚举的实力了。
应该是估算数据量的作用，1000的数量级，不过才怪，我还想着去按位DP。。。。
int n;
int sum_ge[7];
// idx 1 - 3
void calculate(int x,int idx)
{
switch(x) {
case 0: break;
case 1: sum_ge[2*(idx-1)]++; break;
case 2: sum_ge[2*(idx-1)]+=2; break;
case 3: sum_ge[2*(idx-1)]+=3; break;
case 4: sum_ge[2*(idx-1)]+=1;sum_ge[2*(idx-1)+1]++; break;
case 5: sum_ge[2*(idx-1)+1]++; break;
case 6: sum_ge[2*(idx-1)]+=1;sum_ge[2*(idx-1)+1]++; break;
case 7: sum_ge[2*(idx-1)]+=2;sum_ge[2*(idx-1)+1]++; break;
case 8: sum_ge[2*(idx-1)]+=3;sum_ge[2*(idx-1)+1]++; break;
case 9: sum_ge[2*(idx-1)]+=1;sum_ge[2*(idx-1)+2]++; break;
}
}
int main()
{
FOPENTI
FOPENTO
SET(sum_ge,0);
SCF(n);
FOR(i,1,n) {
int t=1,x=i;
while(x) {
calculate(x%10,t++);
x /= 10;
}
}
if(sum_ge[0]) printf("I %d\n",sum_ge[0]);
if(sum_ge[1]) printf("V %d\n",sum_ge[1]);
if(sum_ge[2]) printf("X %d\n",sum_ge[2]);
if(sum_ge[3]) printf("L %d\n",sum_ge[3]);
if(sum_ge[4]) printf("C %d\n",sum_ge[4]);
if(sum_ge[5]) printf("D %d\n",sum_ge[5]);
if(sum_ge[6]) printf("M %d\n",sum_ge[6]);
}
USER: Rain M [m3324631]
TASK: preface
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3048 KB]
Test 2: TEST OK [0.000 secs, 3048 KB]
Test 3: TEST OK [0.000 secs, 3048 KB]
Test 4: TEST OK [0.000 secs, 3048 KB]
Test 5: TEST OK [0.000 secs, 3048 KB]
Test 6: TEST OK [0.000 secs, 3048 KB]
Test 7: TEST OK [0.000 secs, 3048 KB]
Test 8: TEST OK [0.000 secs, 3048 KB]
All tests OK.
YOUR PROGRAM ('preface') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.
Here are the test data inputs:
------- test 1 ----
1
------- test 2 ----
20
------- test 3 ----
100
------- test 4 ----
500
------- test 5 ----
1000
------- test 6 ----
2974
------- test 7 ----
3213
------- test 8 ----
3499
Keep up the good work!
Thanks for your submission!
PROB Subset Sums [ANALYSIS] ---- 明显就是背包，浆糊了。。
// solution 1 求和，DP
// solution 1
// 1： 求和，看是否是整数
// 2： 是的话 DP 和的一半，有多少种组成
// 不可取重复，纠结了很长时间，终于明白了
// 这就是一般背包
int n,sumhalf,ans;
LLong anst[MAXN];
int main()
{
FOPENTI
FOPENTO
SCF(n);
int sum = ((n+1)*n)/2;
if(sum & 0x1) puts("0");
else {
anst[0] = 1;
for(int i = 1;i<=n;i++) {
for(int j = sum/2;j>=i;j--) {
anst[j] += anst[j-i];
}
}
printf("%lld\n",anst[sum/2]/2);
}
}
USER: Rain M [m3324631]
TASK: subset
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3052 KB]
Test 2: TEST OK [0.000 secs, 3052 KB]
Test 3: TEST OK [0.000 secs, 3052 KB]
Test 4: TEST OK [0.000 secs, 3052 KB]
Test 5: TEST OK [0.000 secs, 3052 KB]
Test 6: TEST OK [0.000 secs, 3052 KB]
Test 7: TEST OK [0.000 secs, 3052 KB]
All tests OK.
YOUR PROGRAM ('subset') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.
Here are the test data inputs:
------- test 1 ----
7
------- test 2 ----
15
------- test 3 ----
24
------- test 4 ----
31
------- test 5 ----
36
------- test 6 ----
39
------- test 7 ----
37
Keep up the good work!
Thanks for your submission!
PROB Runaround Numbers [ANALYSIS] ---- 枚举，题目看了好几遍。
限制条件挺多，每位数字不能重复，不能有0，这个数只能是一个环！
unsigned int n;
bool flag;
bool Ans[MAXN];
bool check(unsigned int x)
{
char ss[MAXN];
SET(Ans,false);
int chee = 0;
sprintf(ss,"%u",x);
int len = strlen(ss);
F(i,len) {
if(chee & (1<<(ss[i]-'0'))) return false;
chee |= (1<<(ss[i]-'0'));
}
for(int i = 0;;) {
int k = ss[i] - '0',che = i;
if(k == 0) return false;
if(Ans[i]) {
if(i == 0) flag = 1;
else return false;
break;
}
else Ans[i] = true;
while(k--) {
if(++i >= len) i = 0;
}
if(ss[i] == ss[che]) return false;
}
F(i,len) {
if(!Ans[i]) return false;
}
if(flag)
return true;
}
int main()
{
FOPENTI
FOPENTO
scanf("%u",&n);
while(!check(++n));
printf("%u\n",n);
}
USER: Rain M [m3324631]
TASK: runround
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3048 KB]
Test 2: TEST OK [0.011 secs, 3048 KB]
Test 3: TEST OK [0.000 secs, 3048 KB]
Test 4: TEST OK [0.011 secs, 3048 KB]
Test 5: TEST OK [0.108 secs, 3048 KB]
Test 6: TEST OK [0.065 secs, 3048 KB]
Test 7: TEST OK [0.162 secs, 3048 KB]
All tests OK.
YOUR PROGRAM ('runround') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.
Here are the test data inputs:
------- test 1 ----
99
------- test 2 ----
111110
------- test 3 ----
134259
------- test 4 ----
348761
------- test 5 ----
1000000
------- test 6 ----
5000000
------- test 7 ----
9000000
Keep up the good work!
Thanks for your submission!
PROB Party Lamps [ANALYSIS] ---- 模拟
struct str_hash {
size_t operator()(const string& str) const {
return __stl_hash_string(str.c_str());
}
};
int n,stepgoal;
char goal[105],status[105];
map<string,int> has;
vector<string> vec;
void set_bit(int x,int bol)
{
goal[x-1] = bol + '0';
}
bool findans()
{
F(i,n) {
if(goal[i] == '3') continue;
if(status[i] != goal[i]) return 0;
}
return 1;
}
void dfs(int depth)
{
if(findans()) {
vec.push_back(status);
}
if(depth == stepgoal) {
return;
}
//1
F(i,n) status[i] ='1'-status[i]+'0';
if(!has[status])
has[status] = 1,dfs(depth + 1);
F(i,n) status[i] ='1'-status[i]+'0';
//2
for(int i = 0;i<n;i+=2) {
status[i] ='1'-status[i]+'0';
}
if(!has[status])
has[status] = 1,dfs(depth + 1);
for(int i = 0;i<n;i+=2) {
status[i] ='1'-status[i]+'0';
}
//3
for(int i = 1;i<n;i+=2) {
status[i] ='1'-status[i]+'0';
}
if(!has[status])
has[status] = 1,dfs(depth + 1);
for(int i = 1;i<n;i+=2) {
status[i] ='1'-status[i]+'0';
}
//4
for(int i = 0;i<n;i+=3) {
status[i] ='1'-status[i]+'0';
}
if(!has[status])
has[status] = 1,dfs(depth + 1);
for(int i = 0;i<n;i+=3) {
status[i] ='1'-status[i]+'0';
}
}
int main()
{
FOPENTI
FOPENTO
SCFD(n,stepgoal);
SET(goal,'\0');
F(i,n) goal[i]='3';
int a;
SCF(a);
while(a != -1) {
set_bit(a,1);
SCF(a);
}
SCF(a);
while(a != -1) {
set_bit(a,0);
SCF(a);
}
SET(status,'\0');
F(i,n)status[i] = '1';
has.clear();
has[status] = 1;
dfs(0);
sort(vec.begin(),vec.end());
F(i,vec.size()) {
cout<<vec[i]<<endl;
}
if(vec.size() == 0) {
puts("IMPOSSIBLE");
}
}
一开始忘记 没有答案的时候了。WA了一次
USER: Rain M [m3324631]
TASK: lamps
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3196 KB]
Test 2: TEST OK [0.000 secs, 3196 KB]
Test 3: TEST OK [0.000 secs, 3196 KB]
Test 4: TEST OK [0.000 secs, 3196 KB]
Test 5: TEST OK [0.000 secs, 3196 KB]
Test 6: TEST OK [0.000 secs, 3196 KB]
Test 7: TEST OK [0.000 secs, 3196 KB]
Test 8: TEST OK [0.000 secs, 3196 KB]
All tests OK.
Your program ('lamps') produced all correct answers! This is your
submission #2 for this problem. Congratulations!
Here are the test data inputs:
------- test 1 ----
10
0
-1
-1
------- test 2 ----
10
0
-1
1 -1
------- test 3 ----
20
3
-1
1 3 5 -1
------- test 4 ----
50
100
1 -1
-1
------- test 5 ----
75
250
-1
-1
------- test 6 ----
100
8394
1 7 13 19 25 31 37 43 49 55 -1
64 -1
------- test 7 ----
100
2000
31 86 23 -1
42 -1
------- test 8 ----
100
8950
-1
-1
Keep up the good work!
Thanks for your submission!
good luck