儒略日
题目
思路
毫无思路
反思
非常麻烦的一道题,居然还是第一题!!!看了好久题目感觉做不出来,半个小时就放弃了(还好放弃了)
虽然及时放弃了这道题,但是也浪费了半个小时(不然第二题的错误可能就查出来了),以后还是要多注意时间
动物园
题目
思路
其实不难的一道题(但是目前还不知道为什么会WA)
其实这题很多东西都是迷惑人的,关键是要理解题目
比如说饲料的种类,题目有这么一句话:
数据保证所有 ai 互不相同，所有的 qi 互不相同。
这就意味着q数组连离散化都不需要,q直接赋值为当前下标即可
其他部分细节&优化代码见
关于输出2^64溢出的问题:其实已经想到了这个,但是毕竟大样例都没过,就不管了
反思
- 要仔细理解题目,发现一些细节的东西
- 多注意细节(如
unsigned long long(还好没掉坑里),特判等)
其实当时已经打好对拍并得到了出错数据,但是时间问题就没有再仔细调试,还是要多注意时间安排
代码
考场(40分)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define nn 1000010
#define ll unsigned long long
using namespace std;
ll read() {
ll re = 0 , sig = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')sig = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
re = (re << 1) + (re << 3) + c - '0';
c = getchar();
}
return re * sig;
}
int n , m , c , k;
ll a[nn];
bool buy[nn];
int p[nn] , q[nn];
int main() {
// freopen("zoo.in" , "r" , stdin);
// freopen("zoo.out" , "w" , stdout);
scanf("%d %d %d %d" , &n , &m , &c , &k);
// printf("%d %d %d %d
" , n , m , c , k);
ll pus = 0 , pus2 = 0;
for(int i = 1 ; i <= n ; i++) {
a[i] = read();
// printf("%d " , a[i]);
pus |= a[i];
}
// putchar('
');
for(int i = 1 ; i <= m ; i++) {
p[i] = read(), q[i] = read();
// printf("%d %d
" , p[i] , q[i]);
q[i] = i;
pus2 |= (1 << p[i]);
if((pus >> p[i]) & 1)
buy[i] = true;
}
ll check = 0;
ll cnt = 0;
for(int i = 1 ; i <= m ; i++) {
if(!buy[i]) {
check |= (1 << p[i]) , cnt++;
}
}
check ^= (unsigned)-1ll;
int ans = 0;
if(k <= 20) {
for(ll i = 0 ; i <= (1 << k) - 1 ; i++) {
if((i | check) == check)
ans++;
}
}
else ans = (1 << k) - ((1 << cnt) - 1) * (1 << (k - cnt));
cout << ans - n;
return 0;
}
第二版(60分)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define nn 1000010
#define ll unsigned long long
using namespace std;
ll read() {
ll re = 0 , sig = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')sig = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
re = (re << 1) + (re << 3) + c - '0';
c = getchar();
}
return re * sig;
}
int n , m , c , k;
ll a[nn];
bool buy[nn];
int p[nn] , q[nn];
int main() {
// freopen("zoo3.in" , "r" , stdin);
// freopen("zoo.out" , "w" , stdout);
scanf("%d %d %d %d" , &n , &m , &c , &k);
// printf("%d %d %d %d
" , n , m , c , k);
ll pus = 0 , pus2 = 0;
for(int i = 1 ; i <= n ; i++) {
a[i] = read();
// printf("%d " , a[i]);
pus |= a[i];
}
// putchar('
');
for(int i = 1 ; i <= m ; i++) {
p[i] = read(), q[i] = read();
// printf("%d %d
" , p[i] , q[i]);
q[i] = i;
pus2 |= (1 << p[i]);
if((pus >> p[i]) & 1)
buy[i] = true;
}
ll check = 0;
ll cnt = 0;
for(int i = 1 ; i <= m ; i++) {
if(!buy[i]) {
if(((check >> p[i]) & 1) == 0) cnt++;//20分就差在这一个特判
check |= (1 << p[i]);
}
}
check ^= (unsigned)-1ll;
ll ans = 0;
if(k <= 20)
{
for(ll i = 0 ; i <= (1 << k) - 1 ; i++) {
if((i | check) == check)
ans++;
}
}
ans = (1ull << k) - ((1ull << cnt) - 1ull) * (1ull << (k - cnt));
cout << ans - n;
return 0;
}
函数调用
题目
思路
直接模拟的做法不难想到
考虑优化
不难想到可以用线段树处理:用懒标记直接处理第二种情况(每个数乘一个相同值)(O(1)),第一种情况(指定元素加上一个值)直接下传即可(O(logn)),最后下传所有懒标记并输出(O(nlogn))
70分到手
至于100分?好像是拓扑+线段树?暂时不知道
反思
其实这题70分并不难,但是要对线段树足够熟练(不然时间不够(特别是前面还有一个恶心题)),所以要先把所有题目看完,做一个整体评估再敲代码
代码(70分)
#include <iostream>
#include <cstdio>
#define nn 1000010
#define ll long long
#define mod 998244353
using namespace std;
int read() {
int re = 0 , sig = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')sig = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
re = (re << 1) + (re << 3) + c - '0';
c = getchar();
}
return re * sig;
}
int n , m , q;
ll a[nn];
int dat1[nn] ,dat2[nn] , ty[nn];
int top = 0;
int g[nn * 5];
struct node{
int l , r , ls , rs;
ll tag;
}tr[nn * 4];
int build(int l , int r) {
static int top = 1;
++top;
int p = top;
tr[p].l = l , tr[p].r = r;
tr[p].tag = 1;
if(l != r) {
int mid = (l + r) / 2;
tr[p].ls = build(l , mid);
tr[p].rs = build(mid + 1 , r);
}
else
tr[p].ls = tr[p].rs = 0;
return p;
}
void spread(int p) {
if(tr[p].l == tr[p].r) {
a[tr[p].l] *= tr[p].tag;
a[tr[p].l] %= mod;
tr[p].tag = 1;
return;
}
tr[tr[p].ls].tag *= tr[p].tag;
tr[tr[p].rs].tag *= tr[p].tag;
tr[tr[p].ls].tag %= mod;
tr[tr[p].rs].tag %= mod;
tr[p].tag = 1;
}
void change(int p , int i , int dat) {
// cout << tr[p].l << ' ' << tr[p].r << endl;
spread(p);
if(tr[p].l == tr[p].r) {
a[tr[p].l] += dat;
a[tr[p].l] %= mod;
return;
}
int mid = (tr[p].l + tr[p].r) / 2;
if(i <= mid)
change(tr[p].ls , i , dat);
else
change(tr[p].rs , i , dat);
}
void GetAns(int p) {
spread(p);
if(tr[p].l == tr[p].r)
return;
GetAns(tr[p].ls);
GetAns(tr[p].rs);
}
int root;
void f(int x) {
if(ty[x] == 1){
change(root , dat1[x] , dat2[x]);
return;
}
if(ty[x] == 2) {
tr[root].tag *= dat1[x];
tr[root].tag %= mod;
return;
}
for(int i = dat1[x] ; i < dat2[x] ; i++)
f(g[i]);
}
int main() {
// freopen("call.in" , "r" , stdin);
// freopen("call.out" , "w" , stdout);
n = read();
for(int i = 1 ; i <= n ; i++)
a[i] = read();
root = build(1 , n);
/* tr[root].tag *= 2;
change(root , 1 , 999);
GetAns(root);
for(int i = 1 ; i <= n ; i++)
printf("%d " , a[i]);
return 0;*/
m = read();
for(int i = 1 ; i <= m ; i++) {
ty[i] = read();
if(ty[i] == 1) {
dat1[i] = read(); dat2[i] = read();
}
else if(ty[i] == 2) {
dat1[i] = read();
}
else {
int tmp = read();
dat1[i] = top;
dat2[i] = tmp + top;
for(int j = dat1[i] ; j < dat2[i] ; j++)
g[j] = read();
top = dat2[i];
}
}
q = read();
for(int i = 1 ; i <= q ; i++) {
f(read());
}
GetAns(root);
for(int i = 1 ; i <= n ; i++)
printf("%d " , a[i]);
return 0;
}
贪吃蛇
题目
思路&反思
原来这是个洛谷黑题
考场也就看了下题目,没怎么想,所以没有思路就是最好的思路
All In All
要先把题目全部看一遍做一个整体评估,在做题,搞不出来的题先放弃,注意安排好时间