关键词:
题目链接:ural 1707. Hypnotoad‘s Secret
题目大意:给定N和M,然后N组s0, t0, Δs, Δt, k,每组能够计算出k个星星的坐标;M组a0, b0, c0, d0, Δa, Δb, Δc,?
Δd, q。每组要求算出q个矩形,推断矩形内是否包括星星,对于q≥20的情况要依据公式计算一个值就可以。
解题思路:计算出全部的星星坐标和矩阵,这个每的说了,将矩阵差分成两点。通过计算出每一个点左下角有多少个星
星,然后用容斥计算出矩阵内是否有点。这个属于线段树的一个应用。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 200904040963LL;
const int maxn = 300000;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], s[maxn << 2];
inline void pushup(int u)
s[u] = s[lson(u)] + s[rson(u)];
void build (int u, int l, int r)
lc[u] = l;
rc[u] = r;
s[u] = 0;
if (l == r)
return;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
void modify(int u, int x)
if (lc[u] == x && x == rc[u])
s[u] += 1;
return;
int mid = (lc[u] + rc[u]) / 2;
if (x <= mid)
modify(lson(u), x);
else
modify(rson(u), x);
pushup(u);
int query(int u, int l, int r)
if (l <= lc[u] && rc[u] <= r)
return s[u];
int mid = (lc[u] + rc[u]) / 2, ret = 0;
if (l <= mid)
ret += query(lson(u), l, r);
if (r > mid)
ret += query(rson(u), l, r);
return ret;
struct point
int t, x, y;
point (int x = 0, int y = 0, int t = 0)
set(x, y);
this->t = t;
void set (int x, int y)
this->x = x;
this->y = y;
friend bool operator < (const point& a, const point& b)
if (a.x != b.x)
return a.x < b.x;
if (a.y != b.y)
return a.y < b.y;
return a.t < b.t;
;
struct state
point a, b;
state (point a, point b)
this->a = a;
this->b = b;
;
int N, M, P;
ll T[350];
vector<int> pos, tmp, cnt;
vector<point> vec;
vector<state> que;
map<point, int> G;
inline void add_point (ll x, ll y, int k)
vec.push_back(point(x, y, k));
tmp.push_back(y);
inline void add_state (int a, int b, int c, int d)
add_point(a - 1, b - 1, 1);
add_point(c, d, 1);
int u = vec.size();
que.push_back(state(vec[u-2], vec[u-1]));
add_point(a - 1, d, 1);
add_point(c, b - 1, 1);
inline int find (int a)
return lower_bound(pos.begin(), pos.end(), a) - pos.begin();
void init ()
G.clear();
cnt.clear();
vec.clear();
que.clear();
pos.clear();
tmp.clear();
int a, b, c, d, aa, bb, cc, dd, k;
for (int i = 0; i < M; i++)
scanf("%d%d%d%d%d", &a, &b, &aa, &bb, &k);
a = (a + N) % N; b = (b + N) % N;
for (int j = 0; j < k; j++)
add_point(a, b, 0);
a = (a + aa + N) % N;
b = (b + bb + N) % N;
scanf("%d", &P);
for (int i = 0; i < P; i++)
scanf("%d%d%d%d", &a, &b, &c, &d);
scanf("%d%d%d%d%d", &aa, &bb, &cc, &dd, &k);
a = (a + N) % N; b = (b + N) % N;
c = (c + N) % N; d = (d + N) % N;
cnt.push_back(k);
for (int j = 0; j < k; j++)
add_state(min(a, b), min(c, d), max(a, b), max(c, d));
a = (a + aa + N) % N; b = (b + bb + N) % N;
c = (c + cc + N) % N; d = (d + dd + N) % N;
sort(vec.begin(), vec.end());
sort(tmp.begin(), tmp.end());
pos.push_back(tmp[0]);
for (int i = 1; i < tmp.size(); i++)
if (tmp[i] != tmp[i-1])
pos.push_back(tmp[i]);
build(1, 0, pos.size());
inline int judge (state u)
return G[u.b] + G[u.a] - G[point(u.b.x, u.a.y, 1)] - G[point(u.a.x, u.b.y, 1)];
void solve ()
for (int i = 0; i < vec.size(); i++)
if (vec[i].t)
G[vec[i]] = query(1, 0, find(vec[i].y));
else
modify(1, find(vec[i].y));
int mv = 0;
for (int i = 0; i < cnt.size(); i++)
if (cnt[i] > 20)
ll ret = 0;
for (int j = 0; j < cnt[i]; j++)
ret = (ret + (judge(que[mv + j]) > 0 ? 1 : 0) * T[j]) % mod;
printf("%lld", ret);
else
for (int j = 0; j < cnt[i]; j++)
printf("%d", judge(que[mv + j]) > 0 ?
1 : 0);
mv += cnt[i];
printf("\n");
int main ()
T[0] = 1;
for (int i = 1; i <= 345; i++)
T[i] = T[i-1] * 7 % mod;
while (scanf("%d%d", &N, &M) == 2)
init();
solve();
return 0;
ural1822.hugoii'swar树的结构+二分
1822.HugoII‘sWarTimelimit:0.5secondMemorylimit:64MBThegloriousKingHugoIIhasdeclaredawar—awarthatisholy,victorious,almostbloodless,butruinous!Rightafterdeclaringthewarthekinghasstartedsummoningthearmy. 查看详情
ural1997thosearenotthedroidsyou'relookingfor
二分图的最大匹配。每一个$0$与$1$配对,只建立满足时差大于等于$a$或者小于等于$b$的边,如果二分图最大匹配等于$n/2$,那么有解,遍历每一条边输出答案,否则无解。#include<map>#include<set>#include<ctime>#include<cmath... 查看详情
ural1353milliardvasya'sfunction(dp)
题目地址:Ural1353定义dp[i][j]。表示当前位数为i位时,各位数和为j的个数。对于第i位数来说。总能够看成在前i-1位后面加上一个0~9。所以状态转移方程就非常easy出来了:dp[i][j]=dp[i][j]+dp[i][j-1]+dp[i][j-2]+.......+dp[i][j-9];最后统计就可... 查看详情
ural1353milliardvasya'sfunction(dp)
space=1&num=1353">MilliardVasya‘sFunction大意:求1-10^9之间的数中。各数位和为s的数的个数。思路:dp[i][j]表示位数是i的数字各个位之和为j的数的个数(1<=i<=9,1<=j<=81)。先DP出1到9位数上各位之和的个数,(dp[i][j]=dp[i-1][j]... 查看详情
oracle日期转换
...格式是美国格式,所以以下应该可以满足:SELECTTO_DATE('02Mar201006:00:00','DDMONTHYYYYHH24:MI:SS','NLS_DATE_LANGUAGE=American')FROMdual;本回答被提问者采纳 参考技术Bto_date('02Mar201006:00:00','yyyy-mm-ddhh:mm:ss'); 参考技... 查看详情
fun是将ss所指字符串中所有下标为奇数位置上的字母转换为大写(若该位置上不是字母则不换)
...ng.h>voidfun(char*ss)inti;for(i=1;i<strlen(ss);i=i+2)if((ss[i]>='a')&&(ss[i]<='z'))ss[i]=ss[i]-'32';returnss;首先你的fun函数定义的是void类型,不需要返回值,所以returnss是错的,你传入的是ss数组的地址,所以本身就在原数组... 查看详情
c语言编写函数转换字符串大小写
...>voidfun2(char*ss) inti; for(i=1;i<strlen(ss);i+=2) if(ss[i]>='a'&&ss[i]<='z') ss[i]-=32; main() char*ss; intj; scanf("%s",ss); fun2(ss); puts(ss);哪里错了?intj;是复制的时候漏删了参考技术A#include<stdio.h>#include<string.h>vo... 查看详情
sql语句一直报无效数字的错,为啥?
selectcount(in_date)fromcar_goods_infowhereto_date(in_date,'yyyy-MM-ddHH24:mi:ss')betweento_date('2014-04-2500:00:00','yyyy-MM-ddHH24:mi:ss')andto_date('2014-04-2523:59:59','yyyy-MM-ddHH24:mi:ss')groupbyto_char(in_date,'hh24');in_date是varchar2类型... 查看详情
sql语句字符串的嵌套问题
...存储过程up_pages需要传入一个查询条件的字符串execup_page'wherename="ss"'单引号里面有双引号,我这样写以后它提示:列名‘ss'无效。把双引号换成单引号也不对注意:ss不是一个变量,它是一个数值,我该怎么写呢... 查看详情
python字符串str与byte字节相等==判断(代码片段)
python字符串str与byte字节相等==判断if__name__=='__main__':bb=b'zhangphil'#byte类型数据print(bb)print(type(bb))ss=r'zhangphil'print(bb==ss)print(str(bb,encoding='utf-8')==ss)print(str(bb)==ss)print(bb... 查看详情
oracle时间字段是年月日时分秒怎么根据年月日分组
...分这个怎么写sql参考技术A年:groupbyto_char(to_date(sysdate,'yyyy-mm-ddhh24:mi:ss'),'yyyy');月:groupbyto_char(to_date(sysdate,'yyyy-mm-ddhh24:mi:ss'),'yyyy-mm');groupbyto_char(to_date(sysdate,'yyyy-mm-ddhh24:mi:ss'),'yyyymm');日:... 查看详情
将字符串s='ab34aa243dd78eww89'处理为'**34**243**78***89',然后对数字求和,结果为'**7**9**15***17(代码
s=‘ab34aa243dd78eww89‘#s=‘ab34aa000dd78eww89‘#方法1:result=‘‘foriins:ifi.isalpha():result+=‘*‘else:result+=iprint(result)i=0temp=0ss=‘‘#**34**243**78***89whilei<len(result):ifresult[i].isdigit():temp+=int(result[i])else:iftemp!=0:ss+=str(temp)ss+=result[i]temp=0i+=1ss+=str... 查看详情
oracle存储过程调用小技巧(代码片段)
...varchar(20),createtimedate);2、插入测试数据INSERTINTOtt_estVALUES('1','aa',TO_DATE('2017-06-0101:00:00','YYYY-MM-DDHH24:MI:SS'));INSERTINTOtt_estVALUES('2','bb',TO_DATE('2017-06-0102:00:00','YYYY-MM-DDHH24:MI:SS'));INSERTINTOtt_e... 查看详情
ural-1901spaceelevators
题目:NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情
ural2089experiencedcoachtwosat
DescriptionMishatrainsseveralACMteamsattheuniversity.Heisanexperiencedcoach,andhedoesnotunderestimatethemeaningoffriendlyandcollaborativeatmosphereduringtrainingsessions.Itusedtobethatway,butoneofthet 查看详情
ural2020trafficjaminflowertown
2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情
ural1424minibus
MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情
ural1855tradeguildsoferathia
TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情